$\mathbb{T}_{a}\in\mathbb{R}^{|{\mathcal{S}}|\times|{\mathcal{S}}|}$ is a
matrix with the entry indexed by $(s,s^{\prime})$ equal to
$\mathbb{T}(s^{\prime}\mid s,a_{h})$. Here, note given a vector $C$, ${\rm
diag}(C)$ is define as a $|C|\times|C|$ diagonal matrix where the diagonal
element corresponds to $C$. Thus, we have

$\displaystyle\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=\langle\mathbf{m^{\prime}}_{t},\mathbb{O}^{\dagger}\mathbf{q}_{\tau^{a}_{h}}\rangle=\langle(\mathbb{O}^{\dagger})^{\top}\mathbf{m^{\prime}}_{t},\mathbf{q}_{\tau^{a}_{h}}\rangle,$

where ${\bf q}_{\tau^{a}_{h}}\in\mathbb{R}^{|\mathcal{O}|}$ and ${\bf
q}_{\tau^{a}_{h}}(o)=\mathbb{P}(o|\tau^{a}_{h})$. This concludes the proof. ∎

######  Example 2 (Overcomplete POMDPs).

We consider overcomplete POMDPs so that we can permit
$|{\mathcal{S}}|\geq|\mathcal{O}|$.

######  Lemma 15 (Core tests in overcomplete POMDPs).

Recall
${\mathcal{T}}^{K}=\mathcal{O}\times(\mathcal{O}\times\mathcal{A})^{K-1}$.
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},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-
colmun rank for all $h$, ${\mathcal{T}}^{K}$ is a core test set.

###### Proof.

Fix a test $t=(o^{\prime}_{h:h+K-1},a^{\prime}_{h:h+K-2})$ and consider a step
$h\in[H]$. Then,

$\displaystyle\mathbb{P}(o^{\prime}_{h:h+K-1},a^{\prime}_{h:h+K-2}\mid
s_{h};a_{h:h+K-2}\sim\mathcal{U}(\mathcal{A}))$
$\displaystyle=\mathbb{E}[{\textbf{1}}(o_{h:h+K-1}=o^{\prime}_{h:h+K-1},a_{h:h+K-2}=a^{\prime}_{h:h+K-2})\mid
s_{h};a_{h:h+K-2}\sim\mathcal{U}(\mathcal{A}))]$
$\displaystyle=\mathbb{E}[(1/|\mathcal{A}|^{K-1}){\textbf{1}}(o_{h:h+K-1}=o^{\prime}_{h:h+K-1},a_{h:h+K-2}=a^{\prime}_{h:h+K-2})\mid
s_{h};a_{h:h+K-2}\sim do(a^{\prime}_{h:h+K-2})]$
$\displaystyle=\mathbb{E}[(1/|\mathcal{A}|^{K-1}){\textbf{1}}(o_{h:h+K-1}=o^{\prime}_{h:h+K-1})\mid
s_{h};a_{h:h+K-2}\sim do(a^{\prime}_{h:h+K-2})]$
$\displaystyle=(1/|\mathcal{A}|^{K-1})\mathbb{P}(o^{\prime}_{h:h+K-1}\mid
s_{h};do(a^{\prime}_{h:h+K-2})).$

Thus, the assumption that ${\mathcal{T}}^{K}$ is full column rank implies that
that the matrix
$\mathbb{\bar{J}}_{h}\in\mathbb{R}^{|{\mathcal{T}}^{K}|\times|{\mathcal{S}}|}$
with the entry indexed by $(t,s_{h})$ being equal to
$\mathbb{P}(o^{\prime}_{h:h+K-1}\mid s_{h};do(a^{\prime}_{h:h+K-2}))$ is full-
column rank.

Define a $|{\mathcal{T}}^{K}|$-dimensional state
$\mathbf{q}_{\tau^{a}_{h}}=[\mathbb{P}(t\mid\tau^{a}_{h})]_{t\in{\mathcal{T}}^{K}}$
given history $\tau^{a}_{h}$. By definition, we have

$\displaystyle\mathbf{q}_{\tau^{a}_{h}}=\mathbb{\bar{J}}_{h}\mathbf{s}_{\tau^{a}_{h}}$

Using $\mathbb{\bar{J}}_{h}$ is full-column rank, we have
$\mathbf{s}_{\tau^{a}_{h}}=\bar{M}^{\dagger}_{h}\mathbf{q}_{\tau^{a}_{h}}$.
Thus, using the format of ${\bf m^{\prime}}_{t}$ from the proof of Lemma 14,
we can conclude that for any test $t=(o_{h:h+W},a_{h:h+W-1})$, we have
$\mathbb{P}(o_{h:h+W}|\tau;\text{do}(a_{h:h+W-1}))=\langle(\bar{M}^{\dagger}_{h})^{\top}{\bf
m^{\prime}}_{t},{\bf q}_{\tau^{a}_{h}}\rangle$. Thus, this concludes
${\mathcal{T}}^{K}$ is a core test set. ∎

Finally, we present an important property of predictive states, which
corresponds to the Bayesian filter in POMDP.

######  Lemma 16 (Forward dynamics of predictive states).

We have

$\displaystyle\mathbb{P}(t\mid\tau^{a}_{h},a,o)=\mathbf{m}^{\top}_{o,a,t}\mathbf{q}_{\tau^{a}_{h}}/\mathbf{m}^{\top}_{o}\mathbf{q}_{\tau^{a}_{h}}.$

When we define $M_{o,a}\in\mathbb{R}^{|{\mathcal{T}}|\times|{\mathcal{T}}|}$
where rows are $\mathbf{m}_{o,a,t}$ for $t\in{\mathcal{T}}$, we can express
the forward update rule of predictive states as follows:

$\displaystyle\mathbf{q}_{\tau^{a}_{h},a,o}=M_{o,a}\mathbf{q}_{\tau^{a}_{h}}/(\mathbf{m}^{\top}_{o}\mathbf{q}_{\tau^{a}_{h}}).$

###### Proof.

The proof is an application of Bayes’s rule. We denote the observation part of
$t$ by $t^{\mathcal{O}}$ and the action part of $t^{\mathcal{A}}$,
respectively. We have

$\displaystyle\mathbb{P}(t\mid\tau^{a}_{h},a,o)$
$\displaystyle=\mathbb{P}(t^{\mathcal{O}}\mid\tau^{a}_{h},o;\text{do}(a,t^{\mathcal{A}}))$
(by definition)
$\displaystyle=\frac{\mathbb{P}(o,t^{\mathcal{O}}\mid\tau^{a}_{h};\text{do}(a,t^{\mathcal{A}}))}{\mathbb{P}(o;\tau^{a}_{h})}$
(Bayes rule)
$\displaystyle=\mathbf{m}^{\top}_{o,a,t}\mathbf{q}_{\tau^{a}_{h}}/\mathbf{m}^{\top}_{o}\mathbf{q}_{\tau^{a}_{h}}.$
(by definition)

This concludes the proof. ∎

To further understand that why PSR generalizes POMDP, let us re-visit the
undercomplete POMDPs (i.e., $\mathbb{O}$ being full column rank) again. Set
${\mathcal{T}}=\mathcal{O}$. As we see in the proof of Lemma 14, the belief
state ${\bf s}_{\tau}\in\Delta({\mathcal{S}})$ together with $\mathbb{O}$
defines predictive state, i.e., ${\bf q}_{\tau^{a}_{h}}=\mathbb{O}{\bf
s}_{\tau^{a}_{h}}$, with $M_{o,a}=\mathbb{O}\mathbb{T}_{a}{\rm
diag}(\mathbb{O}(o|\cdot))\mathbb{O}^{\dagger}$, and ${\bf
m}^{\top}_{o}={\textbf{1}}^{\top}{\rm
diag}(\mathbb{O}(o|\cdot))\mathbb{O}^{\dagger}$. Note that in POMDPs, matrix
$M_{o,a}$ and vector $\mathbf{m}_{o}$ all contain non-negative entries. On
other hand, in PSRs, $M_{a,o}$ and $\mathbf{m}_{a,o}$ could contain negative
entries. This is the intuitive reason why PSRs are more expressive than POMDPs
[littman2001predictive]. For the formal instance of a finite-dimensional PSR
which cannot be expressed as a finite-dimensional POMDP, refer to
[singh2004predictive, jaeger1998discrete].

###  D.2 Existence of link functions

We discuss the existence and the form of link functions. First, we define
general value link functions with multi-step futures. For notational
simplicity, we assume here that the tests $t\in{\mathcal{T}}$ have the same
length, i.e., there is a $K\in\mathbb{N}^{+}$, such that
${\mathcal{T}}\subset\mathcal{O}^{K}\times\mathcal{A}^{K-1}$.

######  Definition 9 (General value link functions in dynamical systems).

Recall ${\mathcal{T}}\subset\mathcal{O}^{K}\times\mathcal{A}^{K-1}$ is the set
of tests. At time step $h$, general value link functions
$g^{\pi}_{h}:\mathcal{Z}_{h-1}\times\mathcal{O}^{K}\mathcal{A}^{K-1}\to\mathbb{R}$
are defined as solutions to the following:

$\displaystyle\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})=\mathbb{E}[g^{\pi}_{h}(z_{h-1},o_{h:h+K-1},a_{h:h+K-2})\mid\tau^{a}_{h};(a_{h:h+K-2})\sim\rho^{out}].$
(14)

where $\rho^{out}$ is some distribution over the action set
${\mathcal{T}}^{\mathcal{A}}$ induced by the test set, i.e.,
$\\{t^{\mathcal{A}}:t\in{\mathcal{T}}\\}$. Here, for
$t=(o_{h:h+K-1},a_{h:h+K-2})$, we often denote $o_{h:h+K-1}$ and $a_{h:h+K-2}$
by $t^{\mathcal{O}}$ and $t^{\mathcal{A}}$, respectively.

To show the existence of general value link functions for PSRs, we first study
the format of value functions in PSRs. The following lemma states that value
functions for $M$-memory policies have bilinear forms.

######  Lemma 17 (Bilinear form of value functions for $M$-memory policies).

Let $\phi(\cdot)\in\mathbb{R}^{|\mathcal{Z}_{h-1}|}$ be a one-hot encoding
vector over $\mathcal{Z}_{h-1}$. Suppose ${\mathcal{T}}$ is a core test set.
Then, for any $M$-memory policy $\pi$, there exists
$\mathbb{J}^{\pi}_{h}\in\mathbb{R}^{|\mathcal{Z}_{h-1}|\times|{\mathcal{T}}|}$
such that

$\displaystyle\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})=\phi^{\top}(z_{h-1})\mathbb{J}^{\pi}_{h}{\bf
q}_{\tau^{a}_{h}}.$

###### Proof.

From Lemma 16, there exists a matrix
$M_{o,a}\in\mathbb{R}^{|{\mathcal{T}}|\times|{\mathcal{T}}|}$ such that via
Bayes rule:

$\displaystyle{\bf q}_{\tau^{a}_{h},a,o}=M_{o,a}{\bf
q}_{\tau^{a}_{h}}/\mathbb{P}(o|\tau^{a}_{h}).$ (15)

We use induction to prove the claim. Here, the base argument clearly holds.
Thus, we assume

$\displaystyle\mathcal{V}^{\pi}_{h+1}(\tau^{a}_{h+1})=\phi^{\top}(z_{h})\mathbb{J}^{\pi}_{h+1}{\bf
q}_{\tau^{a}_{h+1}}.$

We have

$\displaystyle\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})$
$\displaystyle=\mathbb{E}[r_{h}+\mathcal{V}^{\pi}_{h+1}(\tau^{a}_{h},o_{h},a_{h})\mid\tau^{a}_{h};a_{h}\sim\pi(\bar{z}_{h})]$
$\displaystyle=\underbrace{\sum_{o_{h},a_{h}}\mathbb{P}(o_{h}\mid\tau^{a}_{h})\pi_{h}(a_{h}\mid
o_{h},z_{h-1})r(o_{h},a_{h})}_{(a)}$
$\displaystyle+\underbrace{\sum_{o_{h},a_{h}}\mathbb{P}(o_{h}\mid\tau^{a}_{h})\pi_{h}(a_{h}\mid
o_{h},z_{h-1})\\{\phi^{\top}(z_{h})\mathbb{J}^{\pi}_{h+1}{\bf
q}_{\tau^{a}_{h},o_{h},a_{h}}\\}}_{(b)}.$

Note we use the assumption that the reward is a function of $o_{h},a_{h}$
conditional on $(\tau^{a}_{h},o_{h},a_{h})$.

We first check the first term (a) that contains rewards. Using the fact that
$\mathbb{P}(o|\tau^{a}_{h})={\bf m}_{o}^{\top}{\bf q}_{\tau^{a}_{h}}$, this is
equal to

$\displaystyle\sum_{o_{h},a_{h}}\langle{\bf
m}_{o_{h}},\mathbf{q}_{\tau^{a}_{h}}\rangle\pi_{h}(a_{h}\mid
o_{h},z_{h-1})r(o_{h},a_{h})=\langle\sum_{o_{h},a_{h}}{\bf
m}_{o_{h}}\pi_{h}(a_{h}\mid
o_{h},z_{h-1})r(o_{h},a_{h}),\mathbf{q}_{\tau^{a}_{h}}\rangle.$

Thus, it has a bilinear form, i.e., there exists some matrix
$\mathbb{J}^{\pi}_{1}$ such that

$\langle\sum_{o_{h},a_{h}}m_{o_{h},a_{h}}\pi_{h}(a_{h}\mid
o_{h},z_{h-1})r_{h},\mathbf{q}_{\tau^{a}_{h}}\rangle=\phi^{\top}(z_{h-1})\mathbb{J}^{\pi}_{1}\mathbf{q}_{\tau^{a}_{h}}$

where $\mathbb{J}^{\pi}_{1}$ is a matrix whose row indexed by $z_{h-1}$ is
equal to $\sum_{o,a}{\bf m}_{o}^{\top}\pi_{h}(a|o,z_{h-1})r(o,a)$.

Next, we see the second term (b). Using (15), the second term is equal to

$\displaystyle\sum_{o_{h},a_{h}}\pi_{h}(a_{h}\mid
o_{h},z_{h-1})\phi^{\top}(z_{h-1}\oplus
o_{h},a_{h})\mathbb{J}^{\pi}_{h+1}M_{o_{h},a_{h}}\mathbf{q}_{\tau^{a}_{h}}$

where we use the notation $z_{h-1}\oplus o,a$ to represent the operation of
appending $(o,a)$ pair to the memory while maintaining the proper length of
the memory by truncating away the oldest observation-action pair. Thus, it has
an again bilinear form $\phi(z_{h-1})^{\top}\mathbb{J}^{\pi}_{2}{\bf
q}_{\tau^{a}_{h}}$ and the matrix $\mathbb{J}^{\pi}_{2}$ can be defined such
that its row indexed by $z_{h-1}$ is equal to
$\sum_{o,a}\pi_{h}(a|o,z_{h-1})\phi^{\top}(z_{h-1}\oplus
o,a)M^{\pi}_{h+1}M_{a,o}$. This concludes the proof. ∎

Next, we check sufficient conditions to ensure the existence of general K-step
link functions. Given ${\mathcal{T}}$, we define the corresponding set of
action sequences ${\mathcal{T}}^{\mathcal{A}}$ as
${\mathcal{T}}^{\mathcal{A}}:=\\{t^{\mathcal{A}}:t\in{\mathcal{T}}\\}$. We set
$\rho^{out}$ in (14) to be a uniform distribution over the set
${\mathcal{T}}^{\mathcal{A}}$ denoted by
$\mathcal{U}({\mathcal{T}}^{\mathcal{A}})$. Namely,
$\mathcal{U}({\mathcal{T}}^{\mathcal{A}})$ will uniformly randomly select a
sequence of test actions from ${\mathcal{T}}^{\mathcal{A}}$.

######  Lemma 18 (Existence of link functions in PSRs).

Suppose ${\mathcal{T}}$ is a core test. There exists
$g^{\pi}_{h}:\mathcal{Z}_{h-1}\times{\mathcal{T}}$ such that

$\displaystyle\mathbb{E}[g^{\pi}_{h}(z_{h-1},o_{h:h+K-1},a_{h:h+K-2})\mid\tau^{a}_{h};a_{h:h+K-2}\sim\mathcal{U}({\mathcal{T}}^{\mathcal{A}})]=\mathcal{V}^{\pi}_{h}(\tau^{a}_{h}).$

###### Proof.

We mainly need to design an unbiased estimator of the predictive state ${\bf
q}_{\tau^{a}_{h}}$. We use importance weighting to do that. Given
$a_{h:h+K-2}\sim\mathcal{U}({\mathcal{T}}^{\mathcal{A}})$, and the resulting
corresponding random observations $o_{h:h+K-1}$, we define the following
estimator $\hat{\bf
q}_{\tau^{a}_{h}}(o_{h:h+K-1},a_{h:h+K-2})\in\mathbb{R}^{|{\mathcal{T}}|}$,
such that its entry indexed by a test $t\in{\mathcal{T}}$ is equal to:

$\displaystyle\hat{\bf
q}_{\tau^{a}_{h}}(o_{h:h+K-1},a_{h:h+K-2})[t]=\frac{{\textbf{1}}(t^{\mathcal{O}}=o_{h:h+K-1},t^{\mathcal{A}}=a_{h:h+K-2})}{1/|{\mathcal{T}}^{\mathcal{A}}|}.$

We can verify that

$\displaystyle\mathbb{E}[\hat{\bf
q}_{\tau^{a}_{h}}(o_{h:h+K-1},a_{h:h+K-2})[t]\mid\tau^{a}_{h};a_{h:h+K-2}\sim\mathcal{U}({\mathcal{T}}^{\mathcal{A}})]$
$\displaystyle=1/|{\mathcal{T}}^{\mathcal{A}}|\mathbb{E}[{\textbf{1}}(t^{\mathcal{O}}=o_{h:h+K-1},t^{\mathcal{A}}=a_{h:h+K-2})\mid\tau^{a}_{h};a_{h:h+K-2}\sim\mathcal{U}({\mathcal{T}}^{\mathcal{A}})]$
$\displaystyle=\mathbb{E}[{\textbf{1}}(t^{\mathcal{O}}=o_{h:h+K-1},t^{\mathcal{A}}=a_{h:h+K-2})\mid\tau^{a}_{h};a_{h:h+K-2}\sim
do(t^{\mathcal{A}})]={\bf q}_{\tau^{a}_{h}}[t].$

Then,

$\displaystyle\mathbb{E}[\hat{\bf
q}_{\tau^{a}_{h}}(o_{h:h+K-1},a_{h:h+K-2})\mid\tau^{a}_{h};a_{h:h+K-2}\sim\mathcal{U}({\mathcal{T}}^{\mathcal{A}})]={\bf
q}_{\tau^{a}_{h}}.$

With this estimator, now we can define the link function using the bilinear
form of $\mathcal{V}^{\pi}_{h}(\tau)$, i.e.,

$\displaystyle
g^{\pi}_{h}(z_{h-1},o_{h:h+K-1},a_{h:h+K-2})=\phi(z_{h-1})^{\top}\mathbb{J}^{\pi}_{h}{\hat{\bf
q}_{\tau^{a}_{h}}}(o_{h:h+K-1},a_{h:h+K-2}).$

Using the fact that $\hat{\bf q}_{\tau^{a}_{h}}(o_{h:h+K-1},a_{h:h+K-2})$ is
an unbiased estimate of ${\bf q}_{\tau^{a}_{h}}$, we can conclude the proof. ∎

Since PSR models capture POMDP models, our above result directly implies the
existence of the link functions in observable POMDPs as well by using obtained
facts in Example 1 and 2 .

###  D.3 PO-Bilinear Rank Decomoposition

Finally, we calculate the PO-bilinear rank. Here,

$g_{h}\in\\{\mathcal{Z}_{h-1}\times(\mathcal{O}^{K}\mathcal{A}^{K-1})\ni(z_{h-1}\times
t)\mapsto\phi(z_{h-1})^{\top}\mathbb{J}^{\pi}_{h}{\hat{\bf
q}_{\tau^{a}_{h}}}(t)\in\mathbb{R}:\mathbb{J}^{\pi}_{h}\in\mathbb{R}^{\mathcal{Z}_{h-1}\times|{\mathcal{T}}|}\\}.$

The Bellman error for $(g,\pi)$ under a roll-in $\pi^{\prime}$ denoted by
$\mathrm{Br}_{h}(g,\pi;\pi^{\prime})$ is defined as

$\displaystyle-\mathbb{E}[\mathbb{E}[g_{h+1}(z_{h},t^{\mathcal{A}}_{h+1},t^{\mathcal{O}}_{h+1})\mid\tau^{a}_{h+1};t^{\mathcal{A}}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}_{h+1})]+r_{h};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle+\mathbb{E}[g_{h}(z_{h-1},t^{\mathcal{A}}_{h},t^{\mathcal{O}}_{h})\mid\tau^{a}_{h};t^{\mathcal{A}}_{h}\sim
U({\mathcal{T}}^{\mathcal{A}}_{h})];a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi].$

In fact, $\mathrm{Br}_{h}(g,\pi;\pi^{\prime})=0$ for any general value link
functions $g^{\pi}$.

Our goal is to design a loss function $l_{h}(\cdot)$ such that we can estimate
the above Bellman error $\mathrm{Br}_{h}(g,\pi;\pi^{\prime})$ using data from
a _single_ policy. To do that, we design the following randomized action
selection strategy.

Given a action sequence $t^{\mathcal{A}}$ from a test $t$, let us denote
$\bar{t}^{\mathcal{A}}$ as a copy of $t^{\mathcal{A}}$ but starting from the
second action of $t^{\mathcal{A}}$, i.e., if
$t^{\mathcal{A}}=\\{a_{1},a_{2},a_{3}\\}$, then
$\bar{t}^{\mathcal{A}}=\\{a_{2},a_{3}\\}$. Denote
$\bar{\mathcal{T}}^{\mathcal{A}}=\\{\bar{t}^{\mathcal{A}}:t\in{\mathcal{T}}\\}$.
Our random action selection strategy first selects $a_{h}\sim U(\mathcal{A})$
uniformly randomly from $\mathcal{A}$, and then select a sequence of actions
$\bar{\bf a}$ uniformly randomly from
${\mathcal{T}}^{\mathcal{A}}\cup\bar{\mathcal{T}}^{\mathcal{A}}$. Here, we
remark the length of outputs is not fixed (i.e., $\bar{\bf
a}\in{\mathcal{T}}^{\mathcal{A}}$ has length larger than the $\bar{\bf
a}\in\bar{\mathcal{T}}^{\mathcal{A}}$).

As a first step, we define two unbiased estimators for ${\bf
q}_{\tau^{a}_{h}}$ and ${\bf q}_{\tau^{a}_{h+1}}$. Conditioning on history
$\tau^{a}_{h}$, given actions $a_{h}\sim U(\mathcal{A})$ followed by action
sequence $\bar{\bf a}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}\cup\bar{\mathcal{T}}^{\mathcal{A}})$, denote the
corresponding observations as $o_{h},o_{h+1},\dots o_{h+|\bar{\bf
a}_{h+1}|+1}$. We construct unbiased estimators for ${\bf q}_{\tau^{a}_{h}}$
and ${\bf q}_{\tau^{a}_{h+1}}$ as follows. As an unbiased estimator of ${\bf
q}_{\tau^{a}_{h}}$, we define $\hat{\bf q}_{\tau^{a}_{h}}$ with the entry
indexed by test $t^{\prime}\in{\mathcal{T}}$ as follows:

$\displaystyle\hat{\bf q}_{\tau^{a}_{h}}(a_{h},\bar{\bf
a}_{h+1},o_{h:h+|\bar{\bf
a}_{h+1}|+1})[t^{\prime}]=\frac{{\textbf{1}}(\bar{\bf
a}_{h+1}\in\bar{\mathcal{T}}^{\mathcal{A}},(a_{h},\bar{\bf
a}_{h+1})=t^{\prime\mathcal{A}},o_{h:h+|\bar{\bf
a}_{h+1}|+1}=t^{\prime\mathcal{O}})}{1/(2|\mathcal{A}||{\mathcal{T}}^{\mathcal{A}}|)}.$
(16)

Similarly, as an unbiased estimator of ${\bf q}_{\tau^{a}_{h+1}}$, we define
$\hat{\bf q}_{\tau^{a}_{h+1}}$ with the entry indexed by test
$t^{\prime}\in{\mathcal{T}}$ as follows:

$\displaystyle\hat{\bf q}_{\tau^{a}_{h+1}}(a_{h},\bar{\bf
a}_{h+1},o_{h+1:h+|\bar{\bf
a}_{h+1}|+1})[t^{\prime}]=\frac{{\textbf{1}}(\bar{\bf
a}_{h+1}\in{\mathcal{T}}^{\mathcal{A}},\bar{\bf
a}_{h+1}=t^{\prime\mathcal{A}},o_{h+1:h+|\bar{\bf
a}_{h+1}|+1}=t^{\prime\mathcal{O}})}{1/(2|{\mathcal{T}}^{\mathcal{A}}|)}$ (17)

We remark the length of $\bar{\bf a}$ in (16) and the one of (17) are
different.

Then, by using importance sampling, we can verify

$\displaystyle\mathbb{E}[\hat{\bf q}_{\tau^{a}_{h}}(a_{h},\bar{\bf
a}_{h+1},o_{h:h+|\bar{\bf a}_{h+1}|+1})|\tau^{a}_{h};a_{h}\sim
U(\mathcal{A}),\bar{\bf a}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}\cup\bar{\mathcal{T}}^{\mathcal{A}})]$
$\displaystyle={\bf q}_{\tau^{a}_{h}},$ $\displaystyle\mathbb{E}[\hat{\bf
q}_{\tau^{a}_{h+1}}(\bar{\bf a}_{h+1},o_{h+1:h+|\bar{\bf
a}_{h+1}|+1})|\tau^{a}_{h+1};\bar{\bf a}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}\cup\bar{\mathcal{T}}^{\mathcal{A}})]$
$\displaystyle={\bf q}_{\tau^{a}_{h+1}}.$

With the above setup, we can construct the loss function $l$ for estimating
the Bellman error. We set the loss as follows:

$\displaystyle l_{h}({z}_{h-1},a_{h},r_{h},\bar{\bf a}_{h+1},o_{h:h+|\bar{\bf
a}_{h+1}|+1};\pi,g)$ (18)
$\displaystyle=\phi(z_{h-1})^{\top}\mathbb{J}_{h}\hat{\bf
q}_{\tau^{a}_{h}}(a_{h},\bar{\bf a}_{h+1},o_{h:h+|\bar{\bf a}_{h+1}|+1})$
$\displaystyle-\frac{{\textbf{1}}\\{a_{h}=\pi_{h}(\bar{z}_{h})\\}}{1/|\mathcal{A}|}\left(r_{h}+\phi(z_{h})^{\top}\mathbb{J}_{h+1}\hat{\bf
q}_{\tau^{a}_{h+1}}(\bar{\bf a}_{h+1},o_{h+1:h+|\bar{\bf
a}_{h+1}|+1})\right).$

Since we have shown that $\hat{\bf q}_{\tau^{a}_{h}}$ and $\hat{\bf
q}_{\tau^{a}_{h+1}}$ are unbiased estimators of ${\bf q}_{\tau}$ and ${\bf
q}_{\tau^{a}_{h+1}}$, respectively, we can show that for any roll-in policy
$\pi^{\prime}$:

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$
$\displaystyle=-\mathbb{E}[\mathbb{E}[g_{h+1}(z_{h},t^{\mathcal{A}}_{h+1},t^{\mathcal{O}}_{h+1})\mid\tau^{a}_{h+1};t^{\mathcal{A}}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}_{h+1})]+r_{h};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle+\mathbb{E}[g_{h}(z_{h-1},t^{\mathcal{A}}_{h},t^{\mathcal{O}}_{h})\mid\tau^{a}_{h};t^{\mathcal{A}}_{h}\sim
U({\mathcal{T}}^{\mathcal{A}}_{h})];a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle=\mathbb{E}[-\phi(z_{h})^{\top}\mathbb{J}^{\pi}_{h+1}{\bf
q}_{\tau^{a}_{h+1}}-r_{h}+\phi(z_{h-1})^{\top}\mathbb{J}^{\pi}_{h}{\bf
q}_{\tau^{a}_{h}};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle=\mathbb{E}\left[l_{h}(z_{h-1},a_{h},r_{h},\bar{\bf
a}_{h+1},o_{h:h+|\bar{\bf
a}_{h+1}|+1};\pi,g);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
U(\mathcal{A}),\bar{\bf a}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}\cup\bar{\mathcal{T}}^{\mathcal{A}})\right].$

The above shows that we can use $l_{h}(\cdot)$ as a loss function.

##### Summary

We can use the almost similar algorithm as Algorithm 1. The sole difference is
we need to replace $\sigma^{t}_{h}(\pi,g)$ with

$\displaystyle\mathbb{E}_{\mathcal{D}^{t}_{h}}\left[l_{h}(z_{h-1},a_{h},r_{h},\bar{\bf
a}_{h+1},o_{h:h+|\bar{\bf
a}_{h+1}|+1};\pi,g);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
U(\mathcal{A}),\bar{\bf a}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}\cup\bar{\mathcal{T}}^{\mathcal{A}})\right]$

where $\mathcal{D}^{t}_{h}$ is an empirical approximation when executing
$a_{1:h-1}\sim\pi^{t},a_{h}\sim U(\mathcal{A}),\bar{\bf a}_{h+1}\sim
U({\mathcal{T}}^{\mathcal{A}}\cup\bar{\mathcal{T}}^{\mathcal{A}})$.

##### Calculation of PO-bilinear rank

Finally, we prove a PSR belongs to the PO-bilinear class.

######  Lemma 19 (PO-bilinear decomposition).

Let $\mathcal{Q}$ be a minimum core test set contained in ${\mathcal{T}}$. The
PSR model has PO-bilinear rank at most
$|\mathcal{O}|^{M}|\mathcal{A}|^{M}|\mathcal{Q}|$, i.e., there exists two
$|\mathcal{O}|^{M}|\mathcal{A}|^{M}|\mathcal{Q}|$-dimensional mappings
$W_{h}:\Pi\times\mathcal{G}\to\mathbb{R}^{{|\mathcal{O}|^{M}|\mathcal{A}|^{M}|\mathcal{Q}|}}$
and
$X_{h}:\Pi\to\mathbb{R}^{{|\mathcal{O}|^{M}|\mathcal{A}|^{M}|\mathcal{Q}|}}$
such that for any tripe $(\pi,g;\pi^{\prime})$, we have:

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$
$\displaystyle=\mathbb{E}\left[\phi(z_{h-1})^{\top}\mathbb{J}_{h}{\bf
q}_{\tau^{a}_{h}}-r_{h}-\phi(z_{h})^{\top}\mathbb{J}_{h+1}{\bf
q}_{\tau^{a}_{h+1}};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi\right]$
$\displaystyle=\left\langle X_{h}(\pi^{\prime}),W_{h}(\pi,g)\right\rangle.$

###### Proof.

We first take expectation conditional on $\tau^{a}_{h}$. Then, we have

$\displaystyle\phi(z_{h-1})^{\top}\mathbb{J}_{h}{\bf
q}_{\tau^{a}_{h}}-\mathbb{E}\left[r_{h}+\phi(z_{h})^{\top}\mathbb{J}_{h+1}{\bf
q}_{\tau^{a}_{h+1}}\mid\tau^{a}_{h};a_{h}\sim\pi\right]$
$\displaystyle=\phi(z_{h-1})^{\top}\mathbb{J}_{h}{\bf
q}_{\tau^{a}_{h}}+\left(\phi(z_{h-1})^{\top}\mathbb{J}^{\pi}_{1}{\bf
q}_{\tau^{a}_{h}}+\phi(z_{h-1})^{\top}\mathbb{J}^{\pi}_{2}{\bf
q}_{\tau^{a}_{h}}\right),$

where $\mathbb{J}^{\pi}_{1}$ and $\mathbb{J}^{\pi}_{2}$ are some two matrices
as defined in the proof of Lemma 17 from where we have already known that the
$\pi$-induced Bellman backup on a value function which has a bilinear form
gives back a bilinear form value function. Rearrange terms, we get:

$\displaystyle\phi(z_{h-1})^{\top}\mathbb{J}_{h}{\bf
q}_{\tau^{a}_{h}}-\mathbb{E}\left[r_{h}+\phi(z_{h})^{\top}\mathbb{J}_{h+1}{\bf
q}_{\tau^{a}_{h+1}}\mid\tau^{a}_{h};a_{h}\sim\pi\right]=\left\langle\phi(z_{h-1}),(\mathbb{J}_{h}+\mathbb{J}^{\pi}_{1}+\mathbb{J}^{\pi}_{2})\bf{q}_{\tau^{a}_{h}}\right\rangle.$

Now recall that the minimum core test set is
$\mathcal{Q}\subset{\mathcal{T}}$. The final step is to argue that ${\bf
q}_{\tau}$ lives in a subspace whose dimension is $|\mathcal{Q}|$. Since
$\mathcal{Q}$ is a core test set, by definition, we can express ${\bf
q}_{\tau^{a}_{h}}$ using $[\mathbb{P}(t|\tau^{a}_{h})]_{t\in\mathcal{Q}}$,
i.e.,

$\displaystyle\exists
K\in\mathbb{R}^{|{\mathcal{T}}|\times|\mathcal{Q}|},\quad{\bf
q}_{\tau^{a}_{h}}=K[\mathbb{P}(t|\tau^{a}_{h})]_{t\in\mathcal{Q}},$

where the row of $K$ indexed by $t\in{\mathcal{T}}$ is equal to ${\bf k}_{t}$,
where ${\bf k}_{t}$ is the vector that is used to predict
$\mathbb{P}(t|\tau^{a}_{h})={\bf
k}_{t}^{\top}[\mathbb{P}(t|\tau^{a}_{h})]_{t\in\mathcal{Q}}$ whose existences
is ensured by the definition of PSRs. This implies that

$\displaystyle\left\langle\phi(z_{h-1}),(\mathbb{J}_{h}+\mathbb{J}^{\pi}_{1}+\mathbb{J}^{\pi}_{2})\bf{q}_{\tau^{a}_{h}}\right\rangle$
$\displaystyle=\left\langle\phi(z_{h-1}),(\mathbb{J}_{h}+\mathbb{J}^{\pi}_{1}+\mathbb{J}^{\pi}_{2})K[\mathbb{P}(t|\tau^{a}_{h})]_{t\in\mathcal{Q}}\right\rangle$
$\displaystyle=(\phi(z_{h-1})\otimes[\mathbb{P}(t|\tau^{a}_{h})]_{t\in\mathcal{Q}}),\text{vec}((\mathbb{J}_{h}+\mathbb{J}^{\pi}_{1}+\mathbb{J}^{\pi}_{2})K)\rangle.$

Finally, we take expectation with respect to $\tau^{a}_{h}$ then we get
$\mathrm{Br}_{h}(\pi,g;\pi^{\prime})=\langle
X_{h}(\pi^{\prime}),W_{h}(\pi,g)\rangle$ such that

$\displaystyle
X_{h}(\pi^{\prime})=\phi(z_{h-1})\otimes\mathbb{E}[[\mathbb{P}(t|\tau^{a}_{h})]_{t\in\mathcal{Q}};a_{1:h-1}\sim\pi^{\prime}],\quad
W_{h}(\pi,g)=\text{vec}((\mathbb{J}_{h}+\mathbb{J}^{\pi}_{1}+\mathbb{J}^{\pi}_{2})K).$

∎

The key observation here is that the bilinear rank scales with $|\mathcal{Q}|$
but not $|{\mathcal{T}}|$. This is good news since we often cannot identify
exact minimal core test sets; however, it is easy to find core tests including
minimal core tests. Thus, even if we do not know the linear dimension of a
dynamical system a priori, the resulting bilinear rank is the linear dimension
of dynamical systems as long as core sets are large enough so that they
include minimal core tests. This will result in the benefit of sample
complexity as we will see Section K.

##  Appendix E Proof of Theorem 1

We fix the parameters as in Theorem 1. Let

$\displaystyle
l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1})=|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{r_{h}+g_{h+1}(\bar{z}_{h+1})\\}-g_{h}(\bar{z}_{h}).$

We define

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

Then, by our assumption 2 with probability $1-\delta$, we $\forall
t\in[T],\forall h\in[H]$

$\displaystyle\sup_{\pi\in\Pi,g\in\mathcal{G}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\pi,g)]-\mathbb{E}[\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\pi,g)]]|\leq\epsilon_{gen},$
(19)
$\displaystyle\sup_{g_{1}\in\mathcal{G}_{1}}|\mathbb{E}_{\mathcal{D}^{0}}[g_{1}(o_{1})]-\mathbb{E}[\mathbb{E}_{\mathcal{D}^{0}}[g_{1}(o_{1})]]|\leq\epsilon_{ini}.$
(20)

Hereafter, we condition on the above events.

We first show the following lemma. Recall

$\displaystyle\pi^{\star}=\mathop{\mathrm{argmax}}_{\pi\in\Pi}J(\pi).$

######  Lemma 20 (Optimism).

Set $R:=\epsilon^{2}_{gen}$. For all $t\in[T]$,
$(\pi^{\star},g^{\pi^{\star}})$ is a feasible solution of the constrained
program. Furthermore, we have
$J(\pi^{\star})\leq\mathbb{E}[g^{t}_{1}(o_{1})]+2\epsilon_{ini}$ for any
$t\in[T]$, where $g^{t}$ is the value link function selected by the algorithm
in iteration $t$.

###### Proof.

For any $\pi$, we have

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

since $g^{\pi}$ is a value link function in $\mathcal{G}$. This is because

$\displaystyle\mathbb{E}[\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\pi,g^{\pi})]$
$\displaystyle=\mathbb{E}[g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1});a_{1:h-1}\sim\pi^{t},a_{h}\sim\pi]$
(IS sampling) $\displaystyle=\langle W_{h}(\pi,g^{\pi}),X_{h}(\pi^{t})\rangle$
(First assumption in Definition 3) $\displaystyle=0.$ (Second assumption in
Definition 3)

Thus,

$\displaystyle|\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\pi^{\star},g^{\pi^{\star}})]|\leq\epsilon_{gen}.$

using (19) noting $\pi^{\star}\in\Pi,g^{\pi^{\star}}\in\mathcal{G}$. This
implies

$\forall t\in[T],\forall
h\in[H];(\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\pi^{\star},g^{\pi^{\star}})])^{2}\leq\epsilon^{2}_{gen}.$

Hence, $(\pi^{\star},g^{\pi^{\star}})$ is a feasible set for any $t\in[T]$.

Then, we have

$\displaystyle J(\pi^{\star})$
$\displaystyle=\mathbb{E}[g^{\pi^{\star}}_{1}(o_{1})]\leq\mathbb{E}_{\mathcal{D}^{0}}[g^{\pi^{\star}}_{1}(o_{1})]+\epsilon_{ini}$
(Uniform convergence result)
$\displaystyle\leq\mathbb{E}_{\mathcal{D}^{0}}[g^{t}_{1}(o_{1})]+\epsilon_{ini}$
(Using the construction of algorithm)
$\displaystyle\leq\mathbb{E}[g^{t}_{1}(o_{1})]+2\epsilon_{ini}.$ (Uniform
convergence)

∎

######  Remark 5.

Note that

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

holds for general link functions $g^{\pi}$ inDefinition 6 . Thus, the
statement goes through even if we use Definition 6.

Next, we prove the following lemma to upper bound the per step regret.

######  Lemma 21.

For any $t\in[T]$, we have

$\displaystyle J(\pi^{\star})-J(\hat{\pi})\leq\sum_{h=1}^{H}|\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{t})\rangle|+2\epsilon_{ini}.$

###### Proof.

$\displaystyle J(\pi^{\star})-J(\hat{\pi})$ $\displaystyle\leq
2\epsilon_{ini}+\mathbb{E}[g^{t}_{1}(o_{1})]-J(\pi^{t})$ (From optimism)
$\displaystyle=2\epsilon_{ini}+\sum_{h=1}^{H}\mathbb{E}[g^{t}_{h}(\bar{z}_{h})-\\{r_{h}+g^{t}_{h+1}(\bar{z}_{h+1})\\};a_{1:h}\sim\pi^{t}]$
(Performance difference lemma) $\displaystyle\leq
2\epsilon_{ini}+\sum_{h=1}^{H}|\mathbb{E}[g^{t}_{h}(\bar{z}_{h})-\\{r_{h}+g^{t}_{h+1}(\bar{z}_{h+1})\\};a_{1:h}\sim\pi^{t}]|$
$\displaystyle=2\epsilon_{ini}+\sum_{h=1}^{H}|\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{t})\rangle|.$ (First assumption in Definition
3)

∎

######  Lemma 22.

Let $\Sigma_{t,h}=\lambda
I+\sum_{\tau=0}^{t-1}X_{h}(\pi^{\tau})X_{h}(\pi^{\tau})^{\top}$. We have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=1}^{H}\|X_{h}(\pi^{t})\|_{\Sigma^{-1}_{t,h}}\leq
H\sqrt{\frac{d}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)}.$

###### Proof.

We fix $h\in[H]$. Here, we have $\Sigma_{t,h}=\lambda
I+\sum_{\tau=0}^{t-1}X_{h}(\pi^{\tau})X_{h}(\pi^{\tau})^{\top}$. From the
elliptical potential lemma in [agarwal2020pc, Lemma G.2], we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|X_{h}(\pi^{t})\|_{\Sigma^{-1}_{t,h}}\leq\sqrt{\frac{1}{T}\sum_{t=0}^{T-1}\|X_{h}(\pi^{t})\|^{2}_{\Sigma^{-1}_{t,h}}}\leq\sqrt{\frac{1}{T}\ln\frac{\det(\Sigma_{t,h})}{\det(\lambda
I)}}\leq\sqrt{\frac{d}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)}.$

Then,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=0}^{H}\|X_{h}(\pi^{t})\|^{2}_{\Sigma^{-1}_{t,h}}\leq
H\sqrt{\frac{d}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)}.$

∎

######  Lemma 23.

$\displaystyle\|W_{h}(\pi^{t},g^{t})\|^{2}_{\Sigma_{t,h}}\leq 2\lambda
B^{2}_{W}+4T\epsilon^{2}_{gen}.$

###### Proof.

We have

$\displaystyle\|W_{h}(\pi^{t},g^{t})\|^{2}_{\Sigma_{t,h}}=\lambda\|W_{h}(\pi^{t},g^{t})\|^{2}_{2}+\sum_{\tau=0}^{t-1}\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{\tau})\rangle^{2}.$

The first term is upper-bounded by $\lambda B^{2}_{W}$. The second term is
upper-bounded by

$\displaystyle\sum_{\tau=0}^{t-1}\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{\tau})\rangle^{2}$
$\displaystyle=\sum_{\tau=0}^{t-1}\left(\mathbb{E}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\pi^{t},g^{t});a_{1:h-1}\sim\pi^{\tau},a_{h}\sim
U(\mathcal{A})]\right)^{2}$ (First assumption in Definition 3)
$\displaystyle\leq
2\sum_{\tau=0}^{t-1}\mathbb{E}_{\mathcal{D}^{\tau}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\pi^{t},g^{t})]^{2}+2t\epsilon^{2}_{gen}\leq
4T\epsilon^{2}_{gen}.$

From the first line to the second line, we use the definition of bilinear rank
models. From the second line to the third line, we use $(a+b)^{2}\leq
2a^{2}+2b^{2}$. In the last line, we use the constraint on $(\pi^{t},g^{t})$.

∎

Combining lemmas so far, we have

$\displaystyle J(\pi^{\star})-J(\hat{\pi})$
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=1}^{H}|\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{t})\rangle|+2\epsilon_{ini}$ (Use Lemma 21)
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=1}^{H}\|W_{h}(\pi^{t},g^{t})\|_{\Sigma_{t,h}}\|X_{h}(\pi^{t})\|_{\Sigma^{-1}_{t,h}}+2\epsilon_{ini}$
(CS inequality) $\displaystyle\leq H^{1/2}\left[2\lambda
B^{2}_{W}+4T\epsilon^{2}_{gen}\right]^{1/2}\left(\frac{dH}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)\right)^{1/2}+2\epsilon_{ini}.$
(Use Lemma 22 and Lemma 23 )

We set $\lambda$ such that
$B^{2}_{X}/\lambda=B^{2}_{W}B^{2}_{X}/\epsilon^{2}_{gen}+1$ and $T=\left\lceil
2Hd\ln(4Hd(B^{2}_{X}B^{2}_{W}/\tilde{\epsilon}_{gen}+1))\right\rceil$. Then,

$\displaystyle\frac{Hd}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)$
$\displaystyle\leq\frac{Hd}{T}\ln\left(1+\frac{T}{d}\left(\frac{B^{2}_{W}B^{2}_{X}}{\epsilon^{2}_{gen}}+1\right)\right)$
$\displaystyle\leq\frac{Hd}{T}\ln\left(1+\frac{T}{d}\left(\frac{B^{2}_{W}B^{2}_{X}}{\tilde{\epsilon}^{2}_{gen}}+1\right)\right)$
$\displaystyle\leq\frac{Hd}{T}\ln\left(\frac{2T}{d}\left(\frac{B^{2}_{W}B^{2}_{X}}{\tilde{\epsilon}^{2}_{gen}}+1\right)\right)\leq
1$

since $a\ln(bT)/T\leq 1$ when $T=2a\ln(2ab)$.

Finally, the following holds

$\displaystyle J(\pi^{\star})-J(\pi^{T})$ $\displaystyle\leq
H^{1/2}\left[4\lambda
B^{2}_{W}+8T\epsilon^{2}_{gen}\right]^{1/2}+2\epsilon_{ini}$
$\displaystyle\leq H^{1/2}\left[4\lambda
B^{2}_{W}+16\epsilon^{2}_{gen}Hd\ln(4Hd(B^{2}_{X}B^{2}_{W}/\tilde{\epsilon}_{gen}+1))\right]^{1/2}+2\epsilon_{ini}$
(Plug in $T$ ) $\displaystyle\leq
H^{1/2}\left[8\epsilon^{2}_{gen}+16\epsilon^{2}_{gen}Hd\ln(4Hd(B^{2}_{X}B^{2}_{W}/\tilde{\epsilon}_{gen}+1))\right]^{1/2}+2\epsilon_{ini}$
(Plug in $\epsilon_{gen}$ ) $\displaystyle\leq
5\epsilon_{gen}\left[H^{2}d\ln(4Hd(B^{2}_{X}B^{2}_{W}/\tilde{\epsilon}_{gen}+1))\right]^{1/2}+2\epsilon_{ini}.$

##  Appendix F Sample Complexity for Finite Function Classes

Consider cases where $\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 13 (Sample complexity for discrete $\Pi$ and $\mathcal{G}$).

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-bilinear 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 at most

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

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

##### Proof.

We derive the above result. First, we check the uniform convergence result.
Then,

$\displaystyle\epsilon_{gen}=c\max(C_{\mathcal{G}},1)|\mathcal{A}|\sqrt{\ln(|\mathcal{G}_{\max}||\Pi_{\max}|TH/\delta)/m}.$

Thus, we need to set $m$ such that

$\displaystyle J(\pi^{\star})-J(\hat{\pi})\leq
c\max(C_{\mathcal{G}},1)|\mathcal{A}|\sqrt{\ln(|\mathcal{G}_{\max}||\Pi_{\max}|TH/\delta)/m}\sqrt{dH^{2}\ln(H^{3}dB^{2}_{X}B^{2}_{W}m+1)}\leq\epsilon$

where $c$ is some constant and

$\displaystyle T=cHd\ln(HdB^{2}_{X}B^{2}_{W}m+1).$

By organizing the term, the following $m$ is sufficient

$\displaystyle
c\sqrt{\frac{dH^{2}\max(C_{\mathcal{G}},1)^{2}|\mathcal{A}|^{2}\ln(|\mathcal{G}_{\max}||\Pi_{\max}|H^{2}d/\delta)\ln(H^{3}dB^{2}_{X}B^{2}_{W}m)}{m}}\leq\epsilon$

Using Lemma 44, the following $m$ satisfies the condition:

$\displaystyle m=c\frac{B_{1}(\ln
B_{1}B_{2})^{2}}{\epsilon^{2}},B_{1}=dH^{2}\max(C_{\mathcal{G}},1)^{2}|\mathcal{A}|^{2}\ln(|\mathcal{G}_{\max}||\Pi_{\max}|H^{2}d/\delta),B_{2}=H^{3}dB^{2}_{X}B^{2}_{W}.$

Combining all together, the sample complexity is $mTH$, i.e.,

$\displaystyle\tilde{O}\left(\frac{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})}{\epsilon^{2}}\right).\quad\blacksquare$

##  Appendix G Sample Complexity in Observable HSE POMDPs

We revisit the existence of link functions by taking the norm constraint into
account. Then, we consider the PO-bilinear decomposition with certain
$B_{X}\in\mathbb{R}$ and $B_{W}\in\mathbb{R}$. Next, we calculate the uniform
convergence result. Finally, we show the sample complexity result.

We use the following assumptions

######  Assumption 7.

For any $h\in[H]$, the following holds:

  1. 1.

$V^{\pi}_{h}(z_{h-1},s)=\langle\theta^{\pi}_{h},\phi_{h}(z_{h-1},s)\rangle.$

  2. 2.

There exists a matrix $K_{h}$ such that
$\mathbb{E}_{o\sim\mathbb{O}(s)}[\psi_{h}(z_{h-1},o)]=K_{h}\phi_{h}(z_{h-1},s)$
(i.e., conditional embedding of the omission distribution),

  3. 3.

$\|\phi_{h}(\cdot)\|\leq 1,\|\psi_{h}(\cdot)\|\leq
1,\|\theta^{\pi}_{h}\|\leq\Theta_{V},0\leq r_{h}\leq 1,$

  4. 4.

There exists a matrix $T_{\pi;h}$ such that
$\mathbb{E}[\phi_{h}(z_{h},s_{h+1})\mid
z_{h-1},s_{h};a_{h}\sim\pi]=T_{\pi;h}\phi_{h}(z_{h-1},s_{h})$ (i.e.,
conditional embedding of the transition)

  5. 5.

$\Pi$ is finite.

We define

$\displaystyle\sigma_{\min}(K)=\min_{h\in[H]}1/\|K_{h}^{\dagger}\|,\
\sigma_{\max}(K)=\max_{h\in[H]}\|K_{h}\|,\
\sigma_{\max}(T)=\max_{h\in[H]}\|T_{\pi:h}\|,$ $\displaystyle
d_{\phi}=\max_{h\in[H]}d_{\phi_{h}},\quad
d_{\psi}=\max_{h\in[H]}d_{\psi_{h}}.$

##### Existence of link functions.

We show value link functions exist. This is proved by 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 link function. The radius of the parameter space is upper-bounded
by $\Theta_{V}/\sigma_{\min}(K)$. Hence, we set

$\mathcal{G}_{h}=\\{\langle\theta,\psi_{h}(\cdot)\rangle:\|\theta\|\leq\Theta_{V}/\sigma_{\min}(K)\\}.$

Then, the realizability holds.

##### PO-bilinear decomposition.

Recall we derive the PO-bilinear decomposition in Section B.4. Consider a
triple $(\pi^{\prime},\pi,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\mathbb{E}\left[\theta_{h}^{\top}\psi_{h+1}(\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=\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 PO-bilinear structure, i.e.,

$X_{h}(\pi^{\prime})=\mathbb{E}[\phi_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}],\quad
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 PO-bilinear rank is at most
$d_{\phi}=\max_{h}d_{\phi_{h}}$. Thus, based on the above PO-bilinear
decomposition, we set
$\|B_{X}\|=1,\|B_{W}\|=2(1+\sigma_{\max}(T))\sigma_{\max}(K)\Theta_{V}/\sigma_{\min}(K)$.
This is because

$\displaystyle\|K_{h}^{\top}(\theta_{h}-\theta^{\star}_{h})-T_{\pi;h}^{\top}K_{h+1}^{\top}(\theta_{h+1}-\theta^{\star}_{h+1})\|$
$\displaystyle\leq\|K_{h}^{\top}\|(\|\theta_{h}\|+\|\theta^{\star}_{h}\|)+\|T_{\pi;h}^{\top}\|\|K_{h+1}^{\top}\|(\|\theta_{h+1}\|+\|\theta^{\star}_{h+1})\|)$
$\displaystyle\leq
2(1+\sigma_{\max}(T))\sigma_{\max}(K)\Theta_{V}/\sigma_{\min}(K).$

and

$\displaystyle\|\mathbb{E}[\phi_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}]\|\leq\mathbb{E}[\|\phi_{h}(z_{h-1},s_{h})\|;a_{1:h-1}\sim\pi^{\prime}]\leq
1.$

In the above, we use Jensen’s inequality.

##### Uniform convergence.

To invoke Theorem 1, we show the uniform convergence result.

######  Lemma 24 (Uniform convergence of loss functions).

Let $C=\Theta_{V}/(\sigma_{\min}(K))$. Then, with probability $1-\delta$,

$\displaystyle\sup_{\pi\in\Pi,g\in\mathcal{G}}\left|\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\right\\}\right]\right|$
$\displaystyle\leq
5|\mathcal{A}|\\{1+2C\\}\sqrt{\frac{\\{2d_{\psi}\ln(1+Cm)+\ln(|\Pi_{\max}|/\delta)\\}}{m}}$

and

$\displaystyle\sup_{g_{1}\in\mathcal{G}_{1}}|\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}[g_{1}(\bar{z}_{1})|\leq
5C\sqrt{\frac{\\{d_{\psi}\ln(1+Cm)+\ln(|\Pi_{\max}|/\delta)\\}}{m}}.$

###### Proof.

Let $C=\Theta_{V}/\sigma_{\min}(K)$. Define $\mathcal{N}_{\epsilon,h}$ as an
$\epsilon$-net for $\mathcal{G}_{h}$. Then,
$|\mathcal{N}_{\epsilon,h}|\leq(1+C/\epsilon)^{d}$. Then,

$\displaystyle|l_{h}(\cdot;\pi,g)-l_{h}(\cdot;\pi^{\diamond},g^{\diamond})|$
$\displaystyle\leq|\mathcal{A}|\\{\|g_{h}-g^{\diamond}_{h}\|_{\infty}+\|g_{h+1}-g^{\diamond}_{h+1}\|_{\infty}\\}$
$\displaystyle\leq|\mathcal{A}|\\{\|\theta_{h}-\theta^{\diamond}_{h}\|_{2}+\|\theta_{h+1}-\theta^{\diamond}_{h+1}\|_{2}\\}\leq
2|\mathcal{A}|\epsilon.$

Besides, for fixed $\pi\in\Pi,\theta_{h}\in\mathcal{N}_{\epsilon,h}$,
$\theta_{h+1}\in\mathcal{N}_{\epsilon,{h+1}}$, we have

$\displaystyle\left\lvert\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h};\theta_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1};\theta_{h+1})\right\\}\right]\right\rvert\leq|\mathcal{A}|\left(1+2C\right)\sqrt{\frac{\ln(|\Pi_{h}|/\delta)}{m}}.$

Then, for $\forall\pi\in\Pi,\forall\theta_{h}\in\mathcal{N}_{\epsilon,h}$,
$\forall\theta_{h+1}\in\mathcal{N}_{\epsilon,{h+1}}$, we have

$\displaystyle\left\lvert\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h};\theta_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1};\theta_{h+1})\right\\}\right]\right\rvert\leq|\mathcal{A}|\left(1+2C\right)\sqrt{\frac{\ln(|\Pi_{h}||\mathcal{N}_{\epsilon,h}||\mathcal{N}_{\epsilon,h+1}|/\delta)}{m}}.$

Hence, for any
$g_{h}=\langle\theta_{h},\psi_{h}\rangle\in\mathcal{G}_{h},g_{h+1}=\langle\theta_{h+1},\psi_{h+1}\rangle\in\mathcal{G}_{h+1}$,

$\displaystyle\left\lvert\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h};\theta_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1};\theta_{h+1})\right\\}\right]\right\rvert$
$\displaystyle\leq|\mathcal{A}|\left(1+2C\right)\sqrt{\frac{\ln(|\Pi_{h}||\mathcal{N}_{\epsilon,h}||\mathcal{N}_{\epsilon,h+1}|/\delta)}{m}}+4|\mathcal{A}|\epsilon.$

By taking $\epsilon=1/m$, we have $\forall\pi\in\Pi,\forall
g_{h}\in\mathcal{G}_{h},\forall g_{h+1}\in\mathcal{G}_{h+1}$:

$\displaystyle|\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}]|$
$\displaystyle\leq|\mathcal{A}|\\{1+2C\\}\sqrt{\frac{\\{2d\ln(1+Cm)+\ln(|\Pi_{h}|/\delta)\\}}{m}}+\frac{4|\mathcal{A}|}{m}$
$\displaystyle\leq
5|\mathcal{A}|\\{1+2C\\}\sqrt{\frac{\\{2d\ln(1+Cm)+\ln(|\Pi_{h}|/\delta)\\}}{m}}.$

Similarly,

$\displaystyle\forall
g_{1}\in\mathcal{G}_{1};|\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}[g_{1}(\bar{z}_{1})]|$
$\displaystyle\leq
C\sqrt{\frac{\\{d\ln(1+Cm)+\ln(|\Pi_{h}|/\delta)\\}}{m}}+\frac{4}{m}$
$\displaystyle\leq 5C\sqrt{\frac{\\{d\ln(1+Cm)+\ln(|\Pi_{h}|/\delta)\\}}{m}}.$

∎

Finally, we obtain the PAC bound, we need to find $m$ such that

$\displaystyle
c|\mathcal{A}|\max(C,1)\sqrt{\frac{d_{\psi}\ln(\max(C,1)m)+\ln(|\Pi_{\max}|TH/\delta)}{m}}\sqrt{d_{\phi}H^{2}\ln\left(Hd_{\phi}B^{2}_{X}B^{2}_{W}m+1\right)}\leq\epsilon.$

where $c$ is some constant and

$\displaystyle T=cHd_{\phi}\ln(HdB^{2}_{X}B^{2}_{W}m+1).$

By organizing the term, the following $m$ is sufficient:

$\displaystyle
c\sqrt{\frac{\\{d_{\psi}+\ln(d_{\phi}|\Pi_{\max}|H^{2}/\delta)\\}d_{\phi}H^{2}|\mathcal{A}|^{2}\max(C,1)^{2}\ln(\\{C+Hd_{\phi}B^{2}_{X}B^{2}_{W}+1)\\}m)^{2}}{m}}\leq\epsilon.$

By using Lemma 44, we can set

$\displaystyle m=\frac{B_{1}}{\epsilon^{2}}\ln(mB_{1}B_{2})^{2},$
$\displaystyle
B_{1}=\\{d_{\psi}+\ln(d_{\phi}|\Pi_{\max}|H^{2}/\delta)\\}d_{\phi}H^{2}|\mathcal{A}|^{2}\max(C,1)^{2},B_{2}=C+Hd_{\phi}B^{2}_{X}B^{2}_{W}+1.$

Thus, the final sample complexity is

$\displaystyle\tilde{O}\left(\frac{d^{2}_{\phi}\\{d_{\psi}+\ln(|\Pi_{\max}|/\delta)\\}H^{4}|\mathcal{A}|^{2}\max(C,1)^{2}}{\epsilon^{2}}\right)$

where $C=\Theta_{V}/\sigma_{\min}(K)$.

##  Appendix H Sample Complexity in Observable Undercomplete Tabular POMDPs

We revisit the existence of value link functions. Then, we show the PO-
bilinear rank decomposition. After showing the uniform convergence lemma, we
calculate the sample complexity.

##### Existence of value link functions.

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}=\mathbb{I}_{|\mathcal{Z}_{h-1}|}\otimes\mathbb{O}.$

where $\mathbf{1}(z)$ is a one-hot encoding vector over $\mathcal{Z}_{h-1}$,
we can regard the tabular model as an HSE-POMDP. Here is our assumption.

######  Assumption 8.

(a) $0\leq r_{h}\leq 1$, (b) $\mathbb{O}$ is full-column rank and
$\|\mathbb{O}^{\dagger}\|_{1}\leq 1/\sigma_{1}$ for any $h\in[H]$.

Note we use the $1$-norm since this choice is more amenable in the tabular
setting. However, even if the norm bound is given in terms of $2$-norm, we can
still ensure the PAC guarantee (this is because
$\|\mathbb{O}^{\dagger}\|_{1}/\sqrt{|{\mathcal{S}}|}\leq\|\mathbb{O}^{\dagger}\|_{2}\leq\|\mathbb{O}^{\dagger}\|_{1}\sqrt{|\mathcal{O}|}$).

Here, since we assume the reward lies in $[0,1]$, value functions on the
latent state belong to
$\\{\langle\theta,\phi_{h}(\cdot)\rangle:\|\theta\|_{\infty}\leq H\\}$. Here,
letting $V^{\pi}_{h}=\langle\theta^{\pi}_{h},\phi_{h}\rangle$, value link
functions exist by taking
$\langle\theta^{\pi}_{h},\mathbf{1}(z)\times\mathbb{O}^{\dagger}\mathbf{1}(o)\rangle$.
Hence, we take

$\displaystyle\mathcal{G}_{h}=\left\\{(z,o)\mapsto\langle\theta,\mathbf{1}(z)\otimes\mathbb{O}^{\dagger}\mathbf{1}(o)\rangle;\|\theta\|_{\infty}\leq
H\right\\}$

so that the realizability holds. Importantly, we can ensure
$\|\mathcal{G}_{h}\|_{\infty}\leq H/\sigma_{1}$ since

$\displaystyle|\langle\theta,\mathbf{1}(z)\otimes\mathbb{O}^{\dagger}\mathbf{1}(o)\rangle|\leq\|\theta\|_{\infty}\|\mathbf{1}(z)\otimes\mathbb{O}^{\dagger}\mathbf{1}(o)\|_{1}\leq\|\theta\|_{\infty}\|\mathbb{O}^{\dagger}\mathbf{1}(o)\|_{1}\leq
H/\sigma_{1}$

for any $(z,o)\in\mathcal{Z}_{h-1}\times\mathcal{O}$. Note $\mathcal{G}_{h}$
is contained in

$\displaystyle\left\\{\langle\theta,\mathbf{1}(z)\otimes\mathbf{1}(o)\rangle;\|\theta\|_{2}\leq
H|\mathcal{O}|^{M+1}|\mathcal{A}|^{M}/\sigma_{1}\right\\}$ (21)

This is because each
$\langle\theta,\mathbf{1}(z)\otimes\mathbb{O}^{\dagger}\mathbf{1}(o)\rangle$
is equal to $\langle\theta^{\prime},\mathbf{1}(z)\otimes\mathbf{1}(o)\rangle$
for some vector
$\theta^{\prime}\in\mathbb{R}^{|\mathcal{Z}_{h-1}|\times|\mathcal{O}|}$. Here,
denoting the component of $\theta$ corresponding to $z\in\mathcal{Z}_{h-1}$ by
$\theta_{z}\in\mathbb{R}^{|\mathcal{O}|}$, $\theta^{\prime}$ is a vector
stacking $\mathbb{O}^{\dagger}\theta_{z}$ for each $z\in\mathcal{Z}_{h-1}$.
Then, we have

$\displaystyle\|\mathbb{O}^{\dagger}\theta_{z}\|_{2}\leq\|\mathbb{O}^{\dagger}\|_{2}\|\theta_{z}\|_{2}\leq\|\mathbb{O}^{\dagger}\|_{1}\sqrt{|\mathcal{O}|}H\sqrt{|\mathcal{O}|}\leq
H|\mathcal{O}|/\sigma_{1}.$

Hence, $\|\theta^{\prime}\|_{2}\leq|\mathcal{O}|^{M}|\mathcal{A}|^{M}\times
H|\mathcal{O}|/\sigma_{1}$.

##### PO-Bilinear decomposition.

Next, recall we derive the PO-bilinear decomposition:

$\displaystyle\mathbb{E}[\theta^{\top}_{h}\phi_{h}(\bar{z}_{h})-r_{h}-\theta^{\top}_{h+1}\phi_{h+1}(\bar{z}_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle=\langle
K^{\top}_{h}\\{\theta_{h}-\theta^{\pi}_{h}\\}-\\{T_{\pi:h}\\}^{\top}K^{\top}_{h+1}\\{\theta_{h+1}-\theta^{\pi}_{h+1}\\},\mathbb{E}[\phi_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}]\rangle.$

Then, $B_{X}=1$ and $B_{W}=4H|\mathcal{O}|^{M+1}|\mathcal{A}|^{M}/\sigma_{1}$.
We use $\|K^{\top}_{h}\|_{2}=\|\mathbb{O}_{h}\|_{2}\leq
1,\|T^{\top}_{\pi:h}\|_{2}\leq 1$. This is because

$\displaystyle\|K^{\top}_{h}\\{\theta_{h}-\theta^{\pi}_{h}\\}-\\{T_{\pi:h}\\}^{\top}K^{\top}_{h+1}\\{\theta_{h+1}-\theta^{\pi}_{h+1}\\}\|_{2}$
$\displaystyle\leq\|\theta_{h}\|_{2}+\|\theta^{\pi}_{h}\|_{2}+\|\theta_{h+1}\|_{2}+\|\theta^{\pi}_{h+1}\|_{2}\leq
4H|\mathcal{O}|^{M+1}|\mathcal{A}|^{M}/\sigma_{1}.$

In the last line, we use (21).

##### Uniform convergence.

Then, we can obtain the following uniform convergence lemma.

######  Lemma 25.

Let $C=H/\sigma_{1}$ and $d_{\psi}=|\mathcal{O}|^{M+1}|\mathcal{A}|^{M}$.
Then, with probability $1-\delta$,

$\displaystyle\sup_{\pi\in\Pi,g\in\mathcal{G}}\left|\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\right\\}\right]\right|$
$\displaystyle\leq
5|\mathcal{A}|\\{1+2C\\}\sqrt{\frac{\\{d^{2}_{\psi}\ln(1+Cm)+\ln(|\Pi_{h}|/\delta)\\}}{m}}$

and

$\displaystyle\sup_{g_{1}\in\mathcal{G}_{1}}|\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}[g_{1}(\bar{z}_{1})]|\leq
5C\sqrt{\frac{\\{d_{\psi}\ln(1+Cm)+\ln(|\Pi_{h}|/\delta)\\}}{m}}.$

###### Proof.

Let
$d_{\phi}=|{\mathcal{S}}||\mathcal{O}|^{M}|\mathcal{A}|^{M},d_{\psi}=|\mathcal{O}|^{M+1}|\mathcal{A}|^{M}$.

Define $\mathcal{N}_{\epsilon,h}$ as an $\epsilon$-net for
$\\{\theta:\|\theta\|_{2}\leq C\\}$ with respect to $L^{2}$-norm. Define
$\mathcal{N}^{\prime}_{\epsilon,h}$ as an $\epsilon$-net for
$\Pi_{h}:\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})$ with respect to the
following norm:

$\displaystyle
d(\pi,\pi^{\prime})=\max_{\bar{z}_{h-1}\in\bar{Z}_{h-1}}\|\pi(\cdot\mid\bar{z}_{h-1})-\pi^{\prime}(\cdot\mid\bar{z}_{h-1})\|_{1}.$

Then,
$|\mathcal{N}_{\epsilon,h}|\leq(1+C/\epsilon)^{d},|\mathcal{N}^{\prime}_{\epsilon,h}|\leq(1+1/\epsilon)^{d_{\psi}|\mathcal{A}|}$.

Let
$g_{h}=\langle\theta_{h},\psi_{h}\rangle,g^{\diamond}_{h}=\langle\theta^{\diamond}_{h},\psi_{h}\rangle$
where $\psi_{h}$ is a one-hot encoding vector over $\bar{\mathcal{Z}}_{h}$.
Then, when
$\|\theta_{h}-\theta^{\diamond}_{h}\|_{2}\leq\epsilon,\|\theta_{h+1}-\theta^{\diamond}_{h+1}\|_{2}\leq\epsilon,\|\pi_{h}-\pi^{\diamond}_{h}\|_{1}\leq\epsilon$,
we have

$\displaystyle|l_{h}(\cdot;\pi,g)-l_{h}(\cdot;\pi^{\diamond},g^{\diamond})|$
$\displaystyle\leq|\mathcal{A}|\\{\|\pi_{h}-\pi^{\diamond}_{h}\|_{\infty}C+\|g_{h}-g^{\diamond}_{h}\|_{\infty}+\|g_{h+1}-g^{\diamond}_{h+1}\|_{\infty}\\}$
$\displaystyle\leq|\mathcal{A}|\\{\epsilon
C+\|\theta_{h}-\theta^{\diamond}_{h}\|_{2}+\|\theta_{h+1}-\theta^{\diamond}_{h+1}\|_{2}\\}$
$\displaystyle\leq 3|\mathcal{A}|C\epsilon.$

Besides, for fixed
$\pi\in\mathcal{N}^{\prime}_{\epsilon,h},\theta_{h}\in\mathcal{N}_{\epsilon,h}$,
$\theta_{h+1}\in\mathcal{N}_{\epsilon,{h+1}}$, we have

$\displaystyle\left\lvert\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h};\theta_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1};\theta_{h+1})\right\\}\right]\right\rvert\leq|\mathcal{A}|\left(1+2C\right)\sqrt{\frac{\ln(1/\delta)}{m}}.$

Then, for
$\forall\pi\in\mathcal{N}^{\prime}_{\epsilon,h},\forall\theta_{h}\in\mathcal{N}_{\epsilon,h}$,
$\forall\theta_{h+1}\in\mathcal{N}_{\epsilon,{h+1}}$, we have

$\displaystyle\left\lvert\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h};\theta_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1};\theta_{h+1})\right\\}\right]\right\rvert\leq|\mathcal{A}|\left(1+2C\right)\sqrt{\frac{\ln(|\mathcal{N}^{\prime}_{\epsilon,h}||\mathcal{N}_{\epsilon,h}||\mathcal{N}_{\epsilon,h+1}|/\delta)}{m}}.$

Hence, for any
$\pi_{h}\in\Pi_{h},g_{h}=\langle\theta_{h},\psi_{h}\rangle\in\mathcal{G}_{h},g_{h+1}=\langle\theta_{h+1},\psi_{h+1}\rangle\in\mathcal{G}_{h+1}$,

$\displaystyle\left\lvert\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}\left[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left\\{g_{h}(\bar{z}_{h};\theta_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1};\theta_{h+1})\right\\}\right]\right\rvert$
$\displaystyle\leq|\mathcal{A}|\left(1+2C\right)\sqrt{\frac{\ln(|\mathcal{N}^{\prime}_{\epsilon,h}||\mathcal{N}_{\epsilon,h}||\mathcal{N}_{\epsilon,h+1}|/\delta)}{m}}+3|\mathcal{A}|C\epsilon.$

By taking $\epsilon=1/m$, we have $\forall\pi\in\Pi,\forall
g_{h}\in\mathcal{G}_{h},\forall g_{h+1}\in\mathcal{G}_{h+1};$

$\displaystyle|\\{\mathbb{E}_{\mathcal{D}}-\mathbb{E}\\}[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}]|$
$\displaystyle\leq|\mathcal{A}|\\{1+2C\\}\sqrt{\frac{\\{2d_{\psi}\ln(1+Cm)+d_{\psi}|\mathcal{A}|\ln(1+m)+\ln(1/\delta)\\}}{m}}+\frac{3|\mathcal{A}|C}{m}$
$\displaystyle\leq
10|\mathcal{A}|C\sqrt{\frac{\\{d_{\psi}|\mathcal{A}|\ln(1+Cm)+\ln(1/\delta)\\}}{m}}.$

∎

##### Sample Complexity.

Finally, we obtain the PAC bound. We need to find $m$ such that

$\displaystyle
c|\mathcal{A}|C\sqrt{\frac{\\{d_{\psi}|\mathcal{A}|\ln(1+Cm)+\ln(TH/\delta)\\}}{m}}\sqrt{d_{\phi}H^{2}\ln(Hd_{\phi}B^{2}_{X}B^{2}_{W}m+1)}\leq\epsilon.$

where $c$ is some constant and

$\displaystyle T=cHd_{\phi}\ln(HdB^{2}_{X}B^{2}_{W}m+1).$

By organizing terms, we get

$\displaystyle\sqrt{\frac{|\mathcal{A}|^{3}C^{2}d_{\phi}d_{\psi}H^{2}\ln(H^{2}d_{\phi}/\delta)\ln(\\{C+d_{\psi}+Hd_{\phi}B^{2}_{X}B^{2}_{W}\\}m)^{2}}{m}}\leq\epsilon.$

Thus, we need to set

$\displaystyle
m=\tilde{O}\left(\frac{|\mathcal{A}|^{3}C^{2}d_{\phi}d_{\psi}H^{2}\ln(1/\delta)}{\epsilon^{2}}\right)$

Hence, the sample complexity is

$\displaystyle\tilde{O}\left(\frac{|\mathcal{A}|^{3}C^{2}d^{2}_{\phi}d_{\psi}H^{4}\ln(1/\delta)}{\epsilon^{2}}\right).$

By some algebra, it is

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

Later, we prove we can remove $|\mathcal{O}|^{M}$ using the more refined
analysis in Section N.

##### Global optimality.

We use a result in the proof of [golowich2022planning, Theorem 1.2]. We just
set $M=C(1/\sigma_{1})^{4}\ln(SH/\epsilon)$. Note their assumption 1 is
satisfied when $\|\mathbb{O}^{\dagger}\|_{1}\leq(1/\sigma_{1})$. More
specifically, assumption 1 in [golowich2022planning] requires for any $b$ and
$b^{\prime}$, we have

$\displaystyle\|\mathbb{O}b-\mathbb{O}b^{\prime}\|_{1}\geq
1/\sigma_{1}\|b-b^{\prime}\|_{1}.$

This is proved as follows. Note for any $e,e^{\prime}$,

$\displaystyle\|\mathbb{O}^{\dagger}e-\mathbb{O}^{\dagger}e^{\prime}\|_{1}\leq\|\mathbb{O}^{\dagger}\|_{1}\|e-e^{\prime}\|_{1}.$

Then, by setting $e=\mathbb{O}b$ and $e^{\prime}=\mathbb{O}b^{\prime}$, the
assumption 1 is ensured. Here, we use $\mathbb{O}^{\dagger}\mathbb{O}=I$.

##  Appendix I Sample Complexity in Observable Overcomplete Tabular POMDPs

To simplify the presentation, we focus on the case when
$\pi^{out}=U(\mathcal{A})$.

##### Existence of value link functions.

In the tabular case, by setting

$\displaystyle\psi_{h}(z,t^{K})=\mathbf{1}(z)\otimes\mathbf{1}(t^{K}),\phi_{h}(z,s)=\mathbf{1}(z)\otimes\mathbf{1}(s),K_{h}=\mathbb{I}_{|\mathcal{Z}_{h-1}|}\otimes\mathbb{O}^{K}.$

where $\mathbf{1}(z)$ is a one-hot encoding vector over $\mathcal{Z}_{h-1}$
and $\mathbf{1}(t^{K})$ is a one-hot encoding vector over
$\mathcal{Z}^{K}=\mathcal{O}^{K}\times\mathcal{A}^{K-1}$, we can regard the
tabular model as an HSE-POMDP. Here is our assumption.

######  Assumption 9.

(a) $0\leq r_{h}\leq 1$, (b) $\mathbb{O}^{K}$ is full-column rank and
$\|\\{\mathbb{O}^{K}\\}^{\dagger}\|_{1}\leq 1/\sigma_{1}$.

Recall we define $\mathbb{O}^{K}$ in Lemma 3. Since we assume the reward lies
in $[0,1]$, value functions on the latent state belong to
$\\{\langle\theta,\phi_{h}(\cdot)\rangle:\|\theta\|_{\infty}\leq H\\}$. Here,
letting $V^{\pi}_{h}(\cdot)=\langle\theta^{\pi}_{h},\phi_{h}(\cdot)\rangle$,
value link functions exist by taking
$\langle\theta^{\pi}_{h},\mathbf{1}(z)\otimes\\{\mathbb{O}^{K}\\}^{\dagger}\mathbf{1}(t^{K})\rangle$.
Hence, we take

$\displaystyle\mathcal{G}_{h}=\\{(z,t^{K})\mapsto\langle\theta^{\pi}_{h},\mathbf{1}(z)\otimes\\{\mathbb{O}^{K}\\}^{\dagger}\mathbf{1}(t^{K})\rangle;\|\theta^{\pi}_{h}\|_{\infty}\leq
H\\}$

so that the realizability holds. Importantly, we can ensure
$\|\mathcal{G}_{h}\|_{\infty}\leq H/\sigma_{1}$ as in Section H. Then, as in
Section H, $\mathcal{G}_{h}$ is contained in

$\displaystyle\left\\{\langle\theta,\mathbf{1}(z)\otimes\mathbf{1}(o)\rangle;\|\theta\|_{2}\leq
H|\mathcal{O}|^{M+1}|\mathcal{A}|^{M}/\sigma_{1}\right\\}.$

##### PO-bilinear decomposition.

Next, we derive the PO-bilinear decomposition:

$\displaystyle\mathbb{E}[\theta^{\top}_{h}\phi(z_{h-1},t^{K}_{h})-r_{h}-\theta^{\top}_{h+1}\phi(z_{h-1},t^{K}_{h});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi,a_{h+1:h+K-1}\sim
U(\mathcal{A})]$
$\displaystyle=\langle\\{K_{h}\\}^{\top}\\{\theta_{h}-\theta^{\pi}_{h}\\}-\\{T_{\pi:h}\\}^{\top}\\{K_{h+1}\\}^{\top}\\{\theta_{h+1}-\theta^{\pi}_{h+1}\\},\mathbb{E}[\phi_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}]\rangle.$

Then, $B_{X}=1$ and $B_{W}=4H|\mathcal{O}|^{M+1}|\mathcal{A}|^{M}/\sigma_{1}$.
We use $\|K_{h}\|_{2}=\|\mathbb{O}^{K}\|_{2}\leq
1,\|T^{\top}_{\pi:h}\|_{2}\leq 1$.

##### Sample Complexity.

We can follow the same procedure in the proof of Section H. Let
$d_{\phi}=|{\mathcal{S}}||\mathcal{O}|^{M}|\mathcal{A}|^{M},d_{\psi}=|\mathcal{O}|^{M+K}|\mathcal{A}|^{M+K-1}$.
Hence, the sample complexity is

$\displaystyle\tilde{O}\left(\frac{|\mathcal{A}|^{3}C^{2}d^{2}_{\phi}d_{\psi}H^{4}\ln(1/\delta)}{\epsilon^{2}\sigma^{2}_{1}}\right).$

By some algebra, the above is

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

Using the more refined analysis later, we show we can remove
$|\mathcal{O}|^{3M+K}$ in Section N.

##  Appendix J Sample Complexity in LQG

In this section, we derive the sample complexity in LQG. We first explain the
setting. Then, we prove the existence of link functions. Lemma 5 is proved
there. Furtheremore, we show the PO-bilinear rank decomposition in LQG. We
prove Lemma 5 there. Next, we show the uniform convergence result in LQG.
Finally, by invoking Theorem 1, we calculate the sample complexity.

We study a finite-horizon discrete time LQG governed by the following
equation:

$\displaystyle
s_{1}=\epsilon_{1},s_{h+1}=As_{h}+Ba_{h}+\epsilon_{h},r_{h}=s^{\top}_{h}Qs_{h}+a^{\top}_{h}Ra_{h},o_{h}=Os_{h}+\tau_{h}.$

where $\epsilon_{h}$ is a Gaussian noise with mean $0$ and noise
$\Sigma_{\epsilon}$ and $\tau_{h}$ is a Gaussian noise with mean $0$ and
$\Sigma_{\tau}$. We use a matrix $O$ instead of $C$ to avoid the notational
confusion later. With a linear policy $\pi_{h}(a_{h}\mid
o_{h},z_{h-1})=\delta(a_{h}=\mathbf{U}_{1h}o_{h}+\mathbf{U}_{2h}z_{h-1})$,
this induces the following system:

$\displaystyle\begin{bmatrix}z^{\prime}_{h}\\\ o_{h}\\\ a_{h}\\\
s_{h+1}\end{bmatrix}=\Xi_{1h}(\pi)\begin{bmatrix}z_{h-1}\\\
s_{h}\end{bmatrix}+\Xi_{2h}(\pi),\Xi_{2h}(\pi)=\begin{bmatrix}0\\\ \tau\\\
\mathbf{U}_{1h}\tau\\\
B\mathbf{U}_{1h}\tau+\epsilon\end{bmatrix},\,\Xi_{1h}(\pi)=\begin{bmatrix}I^{\prime}&0\\\
0&O\\\ \mathbf{U}_{2h}&\mathbf{U}_{1h}O\\\
B\mathbf{U}_{2h}&A+B\mathbf{U}_{1h}O\end{bmatrix}$

where $z^{\prime}_{h}$ is the vector removing $(o_{h},a_{h})$ from $z_{h}$ and
$I^{\prime}$ is a matrix mapping $z_{h}$ to $z^{\prime}_{h}$. This is derived
by

$\displaystyle s_{h+1}$
$\displaystyle=As_{h}+Ba_{h}+\epsilon=As_{h}+B\\{\mathbf{U}_{1h}o_{h}+\mathbf{U}_{2h}z_{h-1}\\}+\epsilon$
$\displaystyle=(A+B\mathbf{U}_{1h}O)s_{h}+B\mathbf{U}_{2h}z_{h-1}+\epsilon+B\mathbf{U}_{1h}\tau,$
$\displaystyle a_{h}$
$\displaystyle=\mathbf{U}_{1h}o_{h}+\mathbf{U}_{2h}z_{h-1}=\mathbf{U}_{1h}Os_{h}+\mathbf{U}_{2h}z_{h-1}+\mathbf{U}_{1h}\tau,$
$\displaystyle o_{h}$ $\displaystyle=Os_{h}+\tau.$

We suppose the system is always stable in the sense that the operator norm of
$\Xi_{1h}(\pi)$ is upper-bounded by $1$. Here is the assumption we introduce
throughout this section.

######  Assumption 10.

Suppose $\max(\|A\|,\|B\|,\|O\|,\|Q\|,\|R\|)\leq\mathbb{C}$. Suppose
$\|\Xi_{1h}(\pi)\|\leq 1$ for any $\pi$. $O$ is full-column rank.

We present the form of linear mean embedding operators in LQGs.

######  Lemma 26 (Linear mean embedding operator).

Let $z\in\mathcal{Z}_{h-1},o\in\mathcal{O},s\in{\mathcal{S}}$. We have

$\displaystyle\mathbb{E}_{o\sim\mathbb{O}(s)}\left[\begin{bmatrix}1\\\
\begin{bmatrix}z\\\ o\end{bmatrix}\otimes\begin{bmatrix}z\\\
o\end{bmatrix}\end{bmatrix}\right]=K_{h}\begin{bmatrix}1\\\
\begin{bmatrix}z\\\ s\end{bmatrix}\otimes\begin{bmatrix}z\\\
s\end{bmatrix}\end{bmatrix},K_{h}=\begin{bmatrix}1&\mathbf{0}\\\
\mathrm{vec}\left(\begin{bmatrix}0&0\\\
0&\Sigma_{\tau}\end{bmatrix}\right)&\begin{bmatrix}\mathbb{I}&0\\\
0&O\end{bmatrix}\otimes\begin{bmatrix}\mathbb{I}&0\\\
0&O\end{bmatrix}.\end{bmatrix}$

###### Proof.

Here, we have

$\displaystyle\mathbb{E}_{o\sim\mathbb{O}(s)}\left[\begin{bmatrix}z\\\
o\end{bmatrix}\otimes\begin{bmatrix}z\\\
o\end{bmatrix}\right]=\mathrm{Vec}\left[\begin{bmatrix}zz^{\top}&zo^{\top}\\\
oz^{\top}&oo^{\top}\end{bmatrix}\right]=\mathrm{Vec}\left[\begin{bmatrix}zz^{\top}&zs^{\top}O^{\top}\\\
Osz^{\top}&Oss^{\top}O^{\top}+\Sigma_{r}\end{bmatrix}\right]$
$\displaystyle=\mathrm{Vec}\left[\begin{bmatrix}0&0\\\
0&\Sigma_{r}\end{bmatrix}\right]+\begin{bmatrix}\mathbb{I}&0\\\
0&O\end{bmatrix}\otimes\begin{bmatrix}\mathbb{I}&O\\\
0&O\end{bmatrix}\times\mathrm{Vec}\left[\begin{bmatrix}zz^{\top}&zs^{\top}\\\
sz^{\top}&ss^{\top}\end{bmatrix}\right].$

From the second line to the third line, we use formula
$\mathrm{vec}[A_{1}A_{2}A_{3}]=(A^{\top}_{3}\otimes
A_{1})\mathrm{vec}(A_{2})$. This immediately concludes the result.

∎

Thus, the matrix $K_{h}$ has the left inverse when $O$ is full-column rank as
follows:

$\displaystyle K^{\dagger}_{h}=\begin{bmatrix}1&\mathbf{0}\\\
-\begin{bmatrix}\mathbb{I}&0\\\
0&O^{\dagger}\end{bmatrix}\otimes\begin{bmatrix}\mathbb{I}&0\\\
0&O^{\dagger}\end{bmatrix}\mathrm{vec}\left(\begin{bmatrix}0&0\\\
0&\Sigma_{\tau}\end{bmatrix}\right)&\begin{bmatrix}\mathbb{I}&0\\\
0&O^{\dagger}\end{bmatrix}\otimes\begin{bmatrix}\mathbb{I}&0\\\
0&O^{\dagger}\end{bmatrix}\end{bmatrix}.$

We use a block matrix inversion formula:

$\displaystyle\begin{bmatrix}A^{-1}_{1}&0\\\
-A^{\dagger}_{3}A_{2}A^{-1}_{1}&A^{\dagger}_{3}\end{bmatrix}\begin{bmatrix}A_{1}&0\\\
A_{2}&A_{3}\end{bmatrix}=I.$

###  J.1 Existence of Link Functions

######  Lemma 27 (Value functions in LQGs).

Let $\pi_{h}(a\mid o,z)=\delta(a=\mathbf{U}_{1h}o+\mathbf{U}_{2h}z)$ for
$z\in\mathcal{Z}_{h-1},o\in\mathcal{O}$. Then, a value function has a bilinear
form:

$\displaystyle
V^{\pi}_{h}(z,s)=[z^{\top},s^{\top}]\Lambda_{h}[z^{\top},s^{\top}]^{\top}+\Gamma_{h}.$

For any $h\in[H]$, these parameters $\Lambda_{h},\Gamma_{h}$ are recursively
defined inductively by

$\displaystyle\Lambda_{H}=\begin{bmatrix}\mathbf{U}^{\top}_{2h}R\mathbf{U}_{2h}&\mathbf{U}^{\top}_{2h}R\mathbf{U}_{1h}O\\\
\\{\mathbf{U}^{\top}_{2h}R\mathbf{U}_{1h}O\\}^{\top}&Q+O^{\top}\mathbf{U}^{\top}_{1h}R\mathbf{U}_{1h}O\end{bmatrix},O_{H}=\mathop{\mathrm{tr}}(\mathbf{U}^{\top}_{1h}R\mathbf{U}_{1h}\Sigma_{\tau}),$
$\displaystyle\Lambda_{h}=\Xi_{1h}(\pi)\Lambda_{h+1}\Xi^{\top}_{1h}(\pi)+\Sigma_{\Lambda_{h}},\Sigma_{\Lambda_{h1}}=\begin{bmatrix}\mathbf{U}^{\top}_{2h}R\mathbf{U}_{2h}&\mathbf{U}^{\top}_{2h}R\mathbf{U}_{1h}O\\\
\\{\mathbf{U}^{\top}_{2h}R\mathbf{U}_{1h}O\\}^{\top}&Q+O^{\top}\mathbf{U}^{\top}_{1h}R\mathbf{U}_{1h}O\end{bmatrix},$
$\displaystyle\Gamma_{h}=\mathop{\mathrm{tr}}\left(\Lambda_{h+1}\Sigma_{\Lambda_{h2}}(\pi)\right)+\Gamma_{h+1},\quad\Sigma_{\Lambda_{h2}}(\pi)=\begin{bmatrix}0&0&0&0\\\
0&\Sigma_{\tau}&\Sigma_{\tau}\mathbf{U}^{\top}_{1h}&\Sigma_{\tau}\mathbf{U}^{\top}_{1h}B^{\top}\\\
0&\mathbf{U}_{1h}\Sigma_{\tau}&\mathbf{U}_{1h}\Sigma_{\tau}\mathbf{U}^{\top}_{1h}&\mathbf{U}_{1h}\Sigma_{\tau}\mathbf{U}^{\top}_{1h}B^{\top}\\\
0&B\mathbf{U}_{1h}\Sigma_{\tau}&B\mathbf{U}_{1h}\Sigma_{\tau}\mathbf{U}^{\top}_{1h}&B\mathbf{U}_{1h}\Sigma_{\tau}\mathbf{U}^{\top}_{1h}B^{\top}+\Sigma_{\epsilon}&\end{bmatrix}.$

###### Proof.

The proof is completed by backward induction regarding $h$, starting from
level $H$. First, we have

$\displaystyle V^{\pi}_{H}(z,s)=s^{\top}Qs+\mathbb{E}_{o\sim
O(s)}[\\{\mathbf{U}_{1h}o+\mathbf{U}_{2h}z\\}^{\top}R\\{\mathbf{U}_{1h}o+K_{2}z\\}]$
$\displaystyle=s^{\top}Qs+\mathbb{E}_{o\sim
O(s)}[\\{\mathbf{U}_{1h}Os+\mathbf{U}_{1h}\tau+\mathbf{U}_{2h}z\\}^{\top}R\\{\mathbf{U}_{1h}Os+\mathbf{U}_{1h}\tau+\mathbf{U}_{2h}z\\}]$
$\displaystyle=s^{\top}\\{Q+O^{\top}\mathbf{U}^{\top}_{1h}R\mathbf{U}_{1h}O\\}s+z\mathbf{U}^{\top}_{2h}R\mathbf{U}_{2h}z+2z^{\top}\mathbf{U}^{\top}_{2h}R\mathbf{U}_{1h}Os+\mathop{\mathrm{tr}}(\mathbf{U}^{\top}_{1h}R\mathbf{U}_{1h}\Sigma_{\tau})$
$\displaystyle=[z^{\top},s^{\top}]\begin{bmatrix}\mathbf{U}^{\top}_{2h}R\mathbf{U}_{2h}&\mathbf{U}^{\top}_{2h}R\mathbf{U}_{1h}O\\\
\\{\mathbf{U}^{\top}_{2h}R\mathbf{U}_{1h}O\\}^{\top}&Q+O^{\top}\mathbf{U}^{\top}_{1h}R\mathbf{U}_{1h}O\end{bmatrix}[z^{\top},s^{\top}]^{\top}+\mathop{\mathrm{tr}}(\mathbf{U}^{\top}_{1h}R\mathbf{U}_{1h}\Sigma_{\tau}).$

Here, we use induction. Thus, supposing the statement is true at horizon
$h+1$, we have

$\displaystyle V^{\pi}_{h}(z,s)$
$\displaystyle=\Gamma_{h+1}+s^{\top}Qs+\mathbb{E}_{o\sim
O(s)}[\\{\mathbf{U}_{1h}o+\mathbf{U}_{2h}z\\}^{\top}R\\{\mathbf{U}_{1h}o+K_{2}z\\}]$
$\displaystyle+\mathbb{E}_{o\sim
O(s),a\sim\pi(o,z),s^{\prime}\sim\mathbb{T}(s,a)}[[z^{\top}_{-1},o^{\top},a^{\top},s^{\prime\top}]\Lambda_{h+1}[z^{\top}_{-1},o^{\top},a^{\top},s^{\prime\top}]^{\top}]$

where $z^{\prime}$ is a vector that removes the last component $(o,a)$ from
$z$ and $s^{\prime}$ is a state at $h+1$. Here, recall we have

$\displaystyle[(z^{\prime})^{\top},o^{\top},a^{\top},s^{\prime\top}]^{\top}=\Xi_{1h}(\pi)[z^{\top},s^{\top}]^{\top}+\Xi_{2h}(\pi).$

Then, the statement is concluded some algebra.

∎

######  Lemma 28 (Norm constraints on value functions).

We can set
$\|\Lambda_{h}\|\leq\mathbb{C}_{\Lambda,h},\|\Gamma_{h}\|\leq\mathbb{C}_{\Gamma,h}$
such that

$\displaystyle\mathbb{C}_{\Lambda,h}=\mathrm{poly}(\mathbb{C},H),\mathbb{C}_{\Gamma,h}=\mathrm{poly}(d_{o},d_{s},d_{a},\mathbb{C},H).$

###### Proof.

We have

$\displaystyle\|\Lambda_{H}\|\leq\mathrm{poly}(\mathbb{C},H),\quad\|\Gamma_{H}\|\leq\mathrm{poly}(\mathbb{C},H).$

Then,

$\displaystyle\|\Lambda_{h}\|\leq\|\Xi_{1h}(\pi)\|\|\Lambda_{h+1}\|\|\Xi_{1h}(\pi)\|+\mathrm{poly}(\mathbb{C},H).$

Since we assume $\|\Xi_{1h}(\pi)\|\leq 1$, this immediately leads to

$\displaystyle\|\Lambda_{h}\|\leq\mathrm{poly}(\mathbb{C},H).$

Besides,

$\displaystyle\|\Gamma_{h}\|\leq\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C})\|\Lambda_{h+1}\|+\|\Gamma_{h+1}\|.$

Thus,

$\displaystyle\|\Gamma_{h}\|\leq\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C}).$

∎

Next, we set the norm on the function class $\mathcal{G}_{h}$.

######  Lemma 29 (Realizability on LQGs).

We set

$\displaystyle\mathcal{G}_{h}=\left\\{\bar{\Gamma}_{h}+(z^{\top},o^{\top})\bar{\Lambda}_{h}(z^{\top},o^{\top})^{\top}\mid\|\bar{\Lambda}_{h}\|\leq
C_{\bar{\Lambda},h},|\bar{\Gamma}_{h}|\leq C_{\bar{\Gamma},h},z\in
Z_{h-1},o\in\mathcal{O}\right\\},$ $\displaystyle
C_{\bar{\Lambda},h}=\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C},\|O^{\dagger}\|),C_{\bar{\Gamma},h}=\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C},\|O^{\dagger}\|).$

A function class $\mathcal{G}_{h}$ includes at least one value link function
for any linear policy $\pi=\delta(a=\mathbf{U}_{1h}o+\mathbf{U}_{2h}z)$ for
$\|\mathbf{U}_{1h}\|\leq\mathbb{C},\|\mathbf{U}_{2h}\|\leq\mathbb{C}$.

###### Proof.

Here, we have

$\displaystyle V^{\pi}_{h}(\cdot)$
$\displaystyle=\Gamma_{h}+\mathop{\mathrm{tr}}\left\\{\Lambda_{h}\begin{bmatrix}zz^{\top}&zs^{\top}\\\
sz^{\top}&ss^{\top}\end{bmatrix}\right\\}$
$\displaystyle=\Gamma_{h}+\mathbb{E}_{o\sim\mathbb{O}(s)}\left[\mathop{\mathrm{tr}}\left\\{\Lambda_{h}\begin{bmatrix}zz^{\top}&zo^{\top}\\{O^{\dagger}\\}^{\top}\\\
O^{\dagger}oz^{\top}&O^{\dagger}\left\\{oo^{\top}-\Sigma_{\tau}\right\\}\\{O^{\dagger}\\}^{\top}\end{bmatrix}\right\\}\right]$
$\displaystyle=\Gamma_{h}-\mathop{\mathrm{tr}}\left\\{\Lambda_{h}\begin{bmatrix}0&0\\\
0&O^{\dagger}\Sigma_{\tau}\\{O^{\dagger}\\}^{\top}\end{bmatrix}\right\\}$
$\displaystyle+\mathbb{E}_{o\sim\mathbb{O}(s)}\left[[z^{\top},o^{\top}]\begin{bmatrix}I&0\\\
0&\\{O^{\dagger}\\}^{\top}\end{bmatrix}\Lambda_{h}\begin{bmatrix}I&0\\\
0&O^{\dagger}\end{bmatrix}\begin{bmatrix}z\\\ o\end{bmatrix}\right].$

The norm constraint on $\bar{\Lambda}_{h}$ is decided by the following
calculation:

$\displaystyle\left\|\begin{bmatrix}I&0\\\
0&\\{O^{\dagger}\\}^{\top}\end{bmatrix}\Lambda_{h}\begin{bmatrix}I&0\\\
0&O^{\dagger}\end{bmatrix}\right\|\leq\|O^{\dagger}\|^{2}_{2}\|\Lambda_{h}\|=\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C},\|O^{\dagger}\|).$

Then, the norm on $\bar{\Gamma}_{h}$ is decided by the following calculation:

$\displaystyle\left\lvert\Gamma_{h}-\mathop{\mathrm{tr}}\left\\{\Lambda_{h}\begin{bmatrix}0&0\\\
0&O^{\dagger}\Sigma_{\tau}\\{O^{\dagger}\\}^{\top}\end{bmatrix}\right\\}\right\rvert$
$\displaystyle\leq|\Gamma_{h}|+\left\lvert\mathop{\mathrm{tr}}\left\\{\Lambda_{h}\begin{bmatrix}0&0\\\
0&O^{\dagger}\Sigma_{\tau}\\{O^{\dagger}\\}^{\top}\end{bmatrix}\right\\}\right\rvert$
$\displaystyle\leq|\Gamma_{h}|+\|\Sigma_{h}\|_{2}\|O^{\dagger}\|^{2}_{2}\mathrm{Tr}(\Sigma_{\tau})$
$\displaystyle\leq|\Gamma_{h}|+\|\Sigma_{h}\|_{2}\|O^{\dagger}\|^{2}_{2}\mathbb{C}d_{o}$
$\displaystyle=\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C},\|O^{\dagger}\|).$

From the first line to the second line, we use Lemma 43.

∎

###  J.2 PO-bilinear Rank Decomposition

######  Lemma 30 (Bilinear rank decomposition for LQG).

For any $g_{h+1}\in\mathcal{G}_{h+1},g_{h}\in\mathcal{G}_{h}$, we have the
following bilinear rank decomposition:

$\displaystyle\mathbb{E}[g_{h+1}(z_{h},o_{h+1})+r_{h}-g_{h}(z_{h-1},o_{h});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]=\langle
X(\pi^{\prime}),W(\pi)\rangle$

where

$\displaystyle
X_{h}(\pi^{\prime})=(1,\mathbb{E}[[z^{\top}_{h-1},s^{\top}_{h}]\otimes[z^{\top}_{h-1},s^{\top}_{h}];a_{1:h-1}\sim\pi^{\prime}])^{\top},$
$\displaystyle
W_{h}(\pi)=\begin{bmatrix}\mathop{\mathrm{tr}}\left(\\{\bar{\Lambda}_{h}-\bar{\Lambda}^{\star}_{h}\\}\begin{bmatrix}0&0\\\
0&\Sigma_{\tau}\end{bmatrix}+\begin{bmatrix}I&0\\\
0&O^{\top}\end{bmatrix}\\{\bar{\Lambda}_{h+1}-\bar{\Lambda}^{\star}_{h+1}\\}\begin{bmatrix}I&0\\\
0&O\end{bmatrix}\Sigma_{\Lambda_{h2}}(\pi)\right)\\\
\mathrm{vec}\left[\begin{bmatrix}I&0\\\
0&O^{\top}\end{bmatrix}\\{\bar{\Lambda}_{h}-\bar{\Lambda}^{\star}_{h}\\}\begin{bmatrix}I&0\\\
0&O\end{bmatrix}+\Xi^{\top}_{1h}(\pi)\begin{bmatrix}I&0\\\
0&O^{\top}\end{bmatrix}\\{\bar{\Lambda}^{\star}_{h+1}-\bar{\Lambda}_{h+1}\\}\begin{bmatrix}I&0\\\
0&O\end{bmatrix}\Xi_{1h}(\pi)\right]\end{bmatrix}.$

Here, $\Xi_{1h}(\pi)$ and $\Sigma_{\Lambda_{h2}}(\pi)$ depend on a policy
$\pi$. The following norm constraints hold:

$\displaystyle\|X_{h}(\pi^{\prime})\|_{2}\leq\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C},\|O^{\dagger}\|),\|W_{h}(\pi)\|_{2}\leq\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C},\|O^{\dagger}\|).$

###### Proof.

We have

$\displaystyle\mathbb{E}[g_{h}(z_{h-1},o_{h})-r_{h}(z_{h-1},s_{h})-g_{h+1}(z_{h},o_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle=-\mathbb{E}[r_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]+$
$\displaystyle+\mathbb{E}\left[\bar{\Gamma}_{h}+(z_{h-1}^{\top},o^{\top}_{h})\bar{\Lambda}_{h}(z_{h-1}^{\top},o^{\top}_{h})^{\top}-\bar{\Gamma}_{h+1}-(z_{h}^{\top},o^{\top}_{h+1})\bar{\Lambda}_{h+1}(z_{h}^{\top},o^{\top}_{h+1})^{\top};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi\right].$
(22)

Since we have

$\displaystyle\mathbb{E}[r_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle=-\mathbb{E}\left[\bar{\Gamma}^{\star}_{h}+(z_{h-1}^{\top},o^{\top}_{h})\bar{\Lambda}^{\star}_{h}(z_{h-1}^{\top},o^{\top}_{h})^{\top}-\bar{\Gamma}^{\star}_{h+1}-(z_{h}^{\top},o^{\top}_{h+1})\bar{\Lambda}^{\star}_{h+1}(z_{h}^{\top},o^{\top}_{h+1})^{\top};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi\right].$

we focus on the term (22).

Hereafter, we suppose the expectation is always taken under
$a_{1:h-1}\sim\pi^{\prime},a\sim\pi$. We also denote
$z=z_{h-1},o_{h}=o,o_{h+1}=o^{\prime},s_{h}=s,s_{h+1}=s^{\prime}$ to simplify
the presentation. Using this simplified notation, we get

$\displaystyle\mathbb{E}\left[(z^{\top},o^{\top})\bar{\Lambda}_{h}(z^{\top},o^{\top})^{\top}\right]=\mathbb{E}\left[(z^{\top},(Os+\tau)^{\top})\bar{\Lambda}_{h}(z^{\top},(Os+\tau)^{\top})^{\top}\right]$
$\displaystyle=\mathbb{E}\left[[z^{\top},s^{\top}]\begin{bmatrix}I&0\\\
0&O^{\top}\end{bmatrix}\bar{\Lambda}_{h}\begin{bmatrix}I&0\\\
0&O\end{bmatrix}\begin{bmatrix}z\\\
s\end{bmatrix}\right]+\mathop{\mathrm{tr}}\left(\bar{\Lambda}_{h}\begin{bmatrix}0&0\\\
0&\Sigma_{\tau}\end{bmatrix}\right).$

Besides,

$\displaystyle\mathbb{E}\left[(z^{\prime\top},o^{\prime\top})\bar{\Lambda}_{h+1}(z^{\prime\top},o^{\prime\top})^{\top}\right]$
$\displaystyle=\mathbb{E}\left[[z^{\prime\top},s^{\prime\top}]\begin{bmatrix}I&0\\\
0&O^{\top}\end{bmatrix}\bar{\Lambda}_{h+1}\begin{bmatrix}I&0\\\
0&O\end{bmatrix}\begin{bmatrix}z^{\prime}\\\
s^{\prime}\end{bmatrix}\right]+\mathop{\mathrm{tr}}\left(\bar{\Lambda}_{h}\begin{bmatrix}0&0\\\
0&\Sigma_{\tau}\end{bmatrix}\right)$
$\displaystyle=\mathbb{E}\left[[z^{\top},s^{\top}]\Xi^{\top}_{1h}(\pi)\begin{bmatrix}I&0\\\
0&O^{\top}\end{bmatrix}\bar{\Lambda}_{h+1}\begin{bmatrix}I&0\\\
0&O\end{bmatrix}\Xi_{1h}(\pi)\begin{bmatrix}z\\\
s\end{bmatrix}\right]+\mathop{\mathrm{tr}}\left(\bar{\Lambda}_{h}\begin{bmatrix}0&0\\\
0&\Sigma_{\tau}\end{bmatrix}\right)+$
$\displaystyle+\mathop{\mathrm{tr}}\left(\begin{bmatrix}I&0\\\
0&O^{\top}\end{bmatrix}\bar{\Lambda}_{h+1}\begin{bmatrix}I&0\\\
0&O\end{bmatrix}\Sigma_{\Lambda_{h2}}(\pi)\right).$

Then, the bilinear decomposition is clear by using

$\displaystyle
A^{\top}_{2}A_{1}A_{2}=\mathrm{tr}(A_{1}A_{2}A^{\top}_{2})=\mathrm{vec}(A^{\top}_{1})^{\top}\mathrm{vec}(A_{2}A^{\top}_{2})=\langle\mathrm{vec}(A^{\top}_{1}),A_{2}\otimes
A_{2}\rangle.$

where $A_{2}$ is any vector and $A_{1}$ is any matrix.

First, we calculate the upper bounds of the norms.

$\displaystyle\|X_{h}(\pi^{\prime})\|^{2}_{2}$
$\displaystyle=1+\left\|\mathbb{E}_{(z,s)\sim
d^{\pi^{\prime}}_{h}}\left[\begin{bmatrix}zz^{\top}&zs^{\top}\\\
sz^{\top}&ss^{\top}\end{bmatrix}\right]\right\|^{2}_{F}$
$\displaystyle=1+\left\|\mathbb{E}_{(z,s)\sim
d^{\pi^{\prime}}_{h-1}}\left[\Xi_{1h}(\pi)\begin{bmatrix}zz^{\top}&zs^{\top}\\\
sz^{\top}&ss^{\top}\end{bmatrix}\Xi^{\top}_{1h}(\pi)\right]+\Sigma_{\Lambda_{h2}}(\pi)\right\|^{2}_{F}$
$\displaystyle\leq 1+\|\Xi_{1h}(\pi)\|^{4}_{2}\left\|\mathbb{E}_{(z,s)\sim
d^{\pi^{\prime}}_{h-1}}\left[\begin{bmatrix}zz^{\top}&zs^{\top}\\\
sz^{\top}&ss^{\top}\end{bmatrix}\right]\right\|^{2}_{F}+\|\Sigma_{\Lambda_{h2}}(\pi)\|^{2}_{F}$
$\displaystyle\leq
1+\|X_{h-1}(\pi^{\prime})\|^{2}_{2}+\|\Sigma_{\Lambda_{h2}}(\pi)\|^{2}_{F}.$

From the third line to the fourth line, we use $\|\Xi_{1h}(\pi)\|_{2}\leq 1$.
Thus,
$\|X_{h}(\pi^{\prime})\|_{2}\leq\mathrm{poly}(H,d_{o},d_{s},d_{a},\|O^{\dagger}\|,\mathbb{C})$.

Next, we consider $W(\pi)$. By some algebra, we can see

$\displaystyle\|W(\pi)\|_{2}$
$\displaystyle\leq\mathrm{poly}(\|\bar{\Lambda}_{h}\|,\|\bar{\Lambda}_{h+1}\|,\mathbb{C},d_{o},d_{s},d_{a},\|\Xi_{1h}(\pi)\|))$
$\displaystyle\leq\mathrm{poly}(H,d_{o},d_{s},d_{a},\|O^{\dagger}\|,\mathbb{C})$

∎

######  Lemma 31 (Variance of marginal distribution).

Recall $d^{\pi}_{h}(z_{h-1},s_{h})$ is a marginal distribution over
$\mathcal{Z}_{h-1}\times{\mathcal{S}}$ at $h$ when we execute
$a_{1:h-1}\sim\pi$. The distribution $d^{\pi}_{h}(z_{h-1},s_{h})$ is a
Gaussian distribution with mean $0$. The operator norm on the variance of
$d^{\pi}_{h}(z_{h-1},s_{h})$ is upper-bounded by
$\mathrm{poly}(H,d_{o},d_{a},d_{s},\mathbb{C})$.

###### Proof.

We first calculate the operator norm of the variance of
$d^{\pi}_{h}(z_{h-1},o_{h})$. The variance is

$\displaystyle\sum_{i=1}^{h}\left(\prod_{t=i+1}^{h}\Xi_{1t}(\pi)\right)\Sigma_{\Lambda_{i2}}(\pi)\left(\prod_{t=i+1}^{h}\Xi^{\top}_{1t}(\pi)\right).$

The statement is immediately concluded. ∎

Let
$u_{h}(\bar{z}_{h},r_{h},a_{h},o_{h+1};\theta)=\theta^{\top}_{h}\psi_{h}(\bar{z}_{h})-r_{h}-\theta^{\top}_{h+1}\psi_{h+1}(\bar{z}_{h+1})$.
Recall
$\psi_{h}(\bar{z}_{h})=[1,\bar{z}^{\top}_{h}\otimes\bar{z}^{\top}_{h}]^{\top}$.
We define

$\displaystyle\hat{y}_{h}(a^{[i]})$
$\displaystyle=\mathbb{E}_{\mathcal{D}}\\{\alpha_{i}(\pi(\bar{z}_{h}))\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\mathbb{I}(\|r_{h}\|\leq Z_{2})\mathbb{I}(\|o_{h+1}\|\leq
Z_{3})\mathbb{I}(a_{h}=a^{[i]})(1+d^{\diamond})$ $\displaystyle
u_{h}(\bar{z}_{h},r_{h},a_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
U(1+d^{\diamond})\\}$ $\displaystyle\hat{y}_{h}(a^{[0]})$
$\displaystyle=\mathbb{E}_{\mathcal{D}}\\{\\{1-\sum_{i}\alpha_{i}(\pi(\bar{z}_{h}))\\}\mathbb{I}(a=0)\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\mathbb{I}(\|r_{h}\|\leq Z_{2})\mathbb{I}(\|o_{h+1}\|\leq Z_{3})$
$\displaystyle(1+d^{\diamond})u_{h}(\bar{z}_{h},r_{h},a_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
U(1+d^{\diamond})\\}.$

Then, the final estimator is constructed by

$\displaystyle\hat{y}_{h}(a^{[0]})+\sum_{i=1}^{d^{\diamond}}\hat{y}_{h}(a^{[i]}).$

This is equal to

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

where

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

We set

$\displaystyle
Z_{i}=\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},H,\|O^{\dagger}\|).$

for any $i\in[3]$.

###  J.3 Uniform Convergence

Recall that

$\displaystyle\Pi=\\{\delta(a=\mathbf{U}_{1h}z+\mathbf{U}_{2h}o)\mid\|\mathbf{U}_{1h}\|\leq\mathbb{C},\|\mathbf{U}_{2h}\|\leq\mathbb{C}\\}.$

Besides, $\mathcal{G}_{h}$ is included in

$\displaystyle\\{\langle\theta,\psi_{h}(\cdot)\rangle\mid\|\theta\|\leq\mathrm{poly}(H,d_{o},d_{s},d_{a},\mathbb{C},\|O^{\dagger}\|)\\}.$

######  Lemma 32 (Concentration of loss functions).

With probability $1-\delta$,

$\displaystyle\sup_{\pi\in\Pi,\theta\in\Theta}|(\mathbb{E}_{\mathcal{D}}-\mathbb{E})\\{l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi)\\}|$

is upper-bounded by

$\displaystyle\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},H,\|O^{\dagger}\|)\times\sqrt{\ln(1/\delta)/m}.$

###### Proof.

Due to indicator functions,
$l_{h}(\bar{z}_{h},a_{h},o_{h},o_{h+1};\theta,\pi)$ is bounded for any
$\pi,\theta$ by

$\displaystyle\mathrm{poly}(\ln(m),d_{s},d_{a},d_{o},\mathbb{C},H,\|O^{\dagger}\|).$

Thus, for fixed $\pi$ and $\theta$, we can say that with high probability
$1-\delta$

$\displaystyle\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},H,\|O^{\dagger}\|,\ln(1/\delta))\times\sqrt{1/m}.$

Besides, we can consider a covering number with respect to $l^{\infty}$-norm
for the space of $K$ and $\theta$ since both are bounded. The radius of each
space is upper-bounded by

$\displaystyle\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},H,\|O^{\dagger}\|).$

Thus, by taking uniform bound and considering the bias term due to the
discretization as in the proof of Lemma 24, the statement is concluded. ∎

######  Lemma 33 (Bias terms 1).

Expectation of $\hat{y}_{h}(a^{[i]})$ and $\hat{y}_{h}(a^{[0]})$ are equal to

$\displaystyle y_{h}(a^{[i]})+\mathrm{Error}_{1},\quad
y_{h}(a^{[0]})+\mathrm{Error}_{2}.$

where

$\displaystyle y_{h}(a^{[i]})$
$\displaystyle=\mathbb{E}\left[\alpha_{i}(\pi(\bar{z}_{h}))\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})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],$ $\displaystyle y_{h}(a^{[0]})$
$\displaystyle=\mathbb{E}\left[\\{1-\sum_{i}\alpha_{i}(\pi(\bar{z}_{h}))\\}\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})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\mathrm{Error}_{1}$
$\displaystyle=m^{-1}\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},H,\|O^{\dagger}\|),\quad\mathrm{Error}_{2}=m^{-1}\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},H,\|O^{\dagger}\|).$

###### Proof.

We want to upper bound the difference of

$\displaystyle\mathbb{E}\left[\alpha_{i}(\pi(\bar{z}_{h}))\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})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]$

and

$\displaystyle\mathbb{E}\left[\alpha_{i}(\pi(\bar{z}_{h}))\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\mathbb{I}(\|r_{h}\|\leq Z_{2})\mathbb{I}(\|o_{h+1}\|\leq
Z_{3})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].$

By CS inequality, we have

$\displaystyle|\mathbb{E}\left[\alpha_{i}(\pi(\bar{z}_{h}))\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\\{\mathbb{I}(\|r_{h}\|\leq Z_{2})\mathbb{I}(\|o_{h+1}\|\leq
Z_{3})-1\\}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]|$
$\displaystyle\leq\underbrace{\left\lvert\mathbb{E}\left[\\{\mathbb{I}(\|r_{h}\|\leq
Z_{2})\mathbb{I}(\|o_{h+1}\|\leq
Z_{3})-1\\}^{2};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
do(a^{[i]})\right]\right\rvert}_{(a)}$
$\displaystyle\times\underbrace{\left\lvert\mathbb{E}\left[\alpha^{2}_{i}(\pi(\bar{z}_{h}))u^{2}_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
do(a^{[i]})\right]\right\rvert^{1/2}}_{(b)}.$

We analyze the term (a) and the term (b). Before starting analysis, note
$(\bar{z}^{\top}_{h},a^{\top}_{h},r^{\top}_{h},o^{\top}_{h+1})$ follows
Gaussian distribution with mean $0$ and variance upper-bounded by

$\displaystyle\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H)$

using Lemma 31. Besides,
$\alpha^{2}_{i}(\pi_{h}(\bar{z}_{h}))\leq\mathrm{poly}(d_{s},d_{o},d_{a},H)$
from Lemma 13. Note we can use a G-optimal design since we have a norm
constraint on $\bar{z}_{1}$.

Regarding the term (a), by setting
$Z_{2}=\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},\ln(m),H,\|O^{\dagger}\|)$
and
$Z_{3}=\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},\ln(m),H,\|O^{\dagger}\|)$
properly, we can ensure it is upper-bounded by

$\displaystyle\frac{\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H,\|O^{\dagger}\|,\ln(m))}{m}.$

Regarding the term (b), noting high order moments of Gaussian distributions
can be always upper-bounded, the term (b) is upper-bounded by
$\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H,\|O^{\dagger}\|,\ln(m))$. This
concludes the statement. ∎

######  Lemma 34 (Bias terms 2).

Recall we define $y_{h}(a^{[i]})$ and $y_{h}(a^{[0]})$ in Lemma 33. Then, we
have

$\displaystyle\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})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})]=y_{h}(a^{[0]})+\sum_{i}y_{h}(a^{[i]}).$

Thus,

$\displaystyle\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
U(1+d^{\diamond})]$
$\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})]+\frac{\mathrm{poly}(\mathbb{C},d_{s},d_{a},d_{o},H,\|O^{\dagger}\|)}{m}.$

###### Proof.

##### First Statement

We have

$\displaystyle\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})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}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\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^{\prime},a_{h}\sim\pi(\bar{z}_{j})]$
$\displaystyle=\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\mathbb{E}[u_{h}(\bar{z}_{h},\pi_{h}(\bar{z}_{h}),r_{h},o_{h+1};\theta)\mid\bar{z}_{h},s_{h},a_{h}=\pi_{h}(\bar{z}_{h})];a_{1:h-1}\sim\pi^{\prime}].$

Here, by some algebra, there exists a vector $c_{2}$

$\displaystyle\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta)\mid\bar{z}_{h},s_{h},a_{h}]=\langle
c_{2},[1,[\bar{z}^{\top}_{h},s^{\top}_{h},a^{\top}_{h}]\otimes[\bar{z}^{\top}_{h},s^{\top}_{h},a^{\top}_{h}]]^{\top}\rangle.$

Thus, there exists $c_{0}$ and a vector $c_{1}$ such that

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

Recall we can write

$\displaystyle\kappa(\pi_{h}(\bar{z}_{h}))=\sum_{i=1}^{d^{\diamond}}\alpha_{i}(\pi_{h}(\bar{z}_{h}))\kappa(a^{[i]})$

Using the above,

$\displaystyle\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})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}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\\{c_{0}(\bar{z}_{h},s_{h})+c^{\top}_{1}(\bar{z}_{h},s_{h})\\}\kappa(\pi_{h}(\bar{z}_{h}));a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle=\mathbb{E}\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\\{c_{0}(\bar{z}_{h},s_{h})+\sum_{i}c^{\top}_{1}(\bar{z}_{h},s_{h})\alpha_{i}(\pi_{h}(\bar{z}_{h}))\kappa(a^{[i]})\\};a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle=\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})[c_{0}(\bar{z}_{h},s_{h})+$
$\displaystyle+\sum_{i}\alpha_{i}(\pi_{h}(\bar{z}_{h}))\\{\mathbb{E}[\kappa(\bar{z}_{h},\pi_{h}(\bar{z}_{h}),r_{h},o_{h+1})\mid\bar{z}_{h},s_{h},a_{h}=a^{[i]}]-c_{0}(\bar{z}_{h},s_{h})\\}];a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle=\mathbb{E}\left[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\left[c_{0}(\bar{z}_{h},s_{h})-\sum_{i}\alpha_{i}(\pi_{h}(\bar{z}_{h}))c_{0}(\bar{z}_{h},s_{h})\right]\right]+\sum_{i}y_{h}(a^{[i]}).$

Besides,

$\displaystyle
c_{0}(\bar{z}_{h},s_{h})=\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta)\mid\bar{z}_{h},s_{h},a_{h}=do(0)].$

Thus,

$\displaystyle\mathbb{E}\left[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\left[c_{0}(\bar{z}_{h},s_{h})-\sum_{i}\alpha_{i}(\pi_{h}(\bar{z}_{h}))c_{0}(\bar{z}_{h},s_{h})\right]\right]$
$\displaystyle=\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\\{1-\sum_{i}\alpha_{i}(\pi_{h}(\bar{z}_{h}))\\}\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta)\mid\bar{z}_{h},s_{h},a_{h}=0];a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle=\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})\\{1-\sum_{i}\alpha_{i}(\pi_{h}(\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}=do(0)]$
$\displaystyle=y_{h}(a^{[0]}).$

In conclusion,

$\displaystyle\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})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})]=y_{h}(a^{[0]})+\sum_{i}y_{h}(a^{[i]}).$

##### Second Statement

As we see in the proof of Lemma 33, the following term

$\displaystyle\mathbb{E}[\\{\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})-1\\}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})]$

is upper-bounded by $\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H,\ln(m))/m.$
Hence,

$\displaystyle\mathbb{E}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi)]$
$\displaystyle=\mathbb{E}[\hat{y}_{h}(a^{[0]})]+\sum_{i=1}^{d^{\diamond}}\mathbb{E}[\hat{y}_{h}(a^{[i]})]$
(Definition)
$\displaystyle=y_{h}(a^{[0]})+\sum_{i=1}^{d^{\diamond}}y_{h}(a^{[i]})+\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H,\ln(m))/m$
(Statement of Lemma 33)
$\displaystyle=\mathbb{E}[\mathbb{I}(\|\bar{z}_{h}\|\leq
Z_{1})u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi_{h}(\bar{z}_{h})]+\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H,\ln(m))/m$
(First statement)
$\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_{h}(\bar{z}_{h})]+\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H,\ln(m))/m$
$\displaystyle=\mathrm{Br}_{h}(\pi,\theta;\pi^{\prime})+\mathrm{poly}(\mathbb{C},d_{s},d_{o},d_{a},H,\ln(m))/m.$

∎

###  J.4 Sample Complexity

Summarizing results so far, we have

$\displaystyle\sup_{\pi\in\Pi,\theta\in\Theta}|\mathbb{E}_{\mathcal{D}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi)\\}]-\mathrm{Br}_{h}(\pi,\theta;\pi^{\prime})|$
$\displaystyle\leq\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},H,\|O^{\dagger}\|)\times\sqrt{\ln(1/\delta)/m}.$

This is enough to invoke Theorem 1. Here, recall we have

$\displaystyle\|X_{h}(\pi)\|\leq\mathrm{poly}(H,d_{o},d_{a},d_{s},\mathbb{C},\Theta,\|O^{\dagger}\|),\quad\|W_{h}(\pi)\|\leq\mathrm{poly}(H,d_{o},d_{a},d_{s},\mathbb{C},\Theta,\|O^{\dagger}\|).$

for any $\pi\in\Pi$ using Lemma 30. In addition, we showed the PO-bilinear
rank is

$\displaystyle\mathrm{poly}(H,d_{o},d_{a},d_{s}).$

Then, using Theorem 1, the sample complexity is

$\displaystyle\tilde{O}\left(\mathrm{poly}(\ln(m),d_{s},d_{o},d_{a},\mathbb{C},\Theta,H,\|O^{\dagger}\|,\ln(1/\delta))\times\frac{1}{\epsilon^{2}}\right).$

##  Appendix K Sample Complexity in PSRs

To focus on the main point, we just use a one-step future. We first show the
form of link functions to set a proper class for $\mathcal{G}_{h}$. Next, we
show the PO-bilinear decomposition.

We assume the following assumptions.

######  Assumption 11.

(a) ${\mathcal{T}}\subset\mathcal{O}$ is a core test and $\mathcal{Q}$ is a
minimum core rest, (b) $\|\mathrm{vec}(\mathbb{J}^{\pi}_{h})\|\leq\Theta$ for
any $\pi\in\Pi$ where $\mathbb{J}^{\pi}_{h}$ is in
$\mathcal{V}^{\pi}_{h}(\tau_{h})={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}_{h}^{\pi}{\bf
q}_{\tau_{h}}$.

###  K.1 Existence of Link Functions

Recall
$V^{\pi}_{h}(\tau_{h})={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}_{h}^{\pi}{\bf
q}_{\tau_{h}}$, where we use
${\textbf{1}}(z)\in\mathbb{R}^{|\mathcal{O}|^{M}|\mathcal{A}|^{M}}$ to denote
the one-hot encoding vector over $\mathcal{Z}_{h-1}$, and
$\mathbb{J}_{h}^{\pi}$ is a matrix in
$\mathbb{R}^{|\mathcal{O}|^{M}|\mathcal{A}|^{M}\times|{\mathcal{T}}|}$.

Then,
$g^{\pi}_{h}(z_{h-1},o):={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}^{\pi}_{h}[{\textbf{1}}(t=o)]_{t\in{\mathcal{T}}}$
is a value link function. This is because

$\displaystyle\mathbb{E}[g_{h}(z_{h-1},o)\mid\tau_{h}]$
$\displaystyle=\mathbb{E}[{\textbf{1}}(z_{h-1})^{\top}\mathbb{J}^{\pi}_{h}[{\textbf{1}}(t=o)]_{t\in{\mathcal{T}}}\mid\tau_{h}]$
$\displaystyle={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}_{h}^{\pi}{\bf
q}_{\tau_{h}}.$

Hence, we set $\mathcal{G}_{h}$ to be

$\displaystyle\\{(z_{h-1},o)\mapsto{\textbf{1}}(z_{h-1})^{\top}\mathbb{J}[{\textbf{1}}(t=o)]_{t\in{\mathcal{T}}}:\|\mathrm{vec}(\mathbb{J})\|\leq\Theta\\}$

so that the realizability holds.

###  K.2 PO-bilinear Rank Decomposition

We show that PSR admits PO-bilinear rank decomposition (Definition 6). Here is
the Bellman loss:

$\displaystyle\mathbb{E}[\\{g_{h+1}(z_{h},o_{h+1})+r_{h}\\}-g_{h}(z_{h-1},o_{h});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi].$

To analyze the above, we decompose the above into three terms:

$\displaystyle\underbrace{\mathbb{E}[g_{h+1}(z_{h},o_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]}_{(a)}+\underbrace{\mathbb{E}[r_{h};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]}_{(b)}+\underbrace{\mathbb{E}[-g_{h}(z_{h-1},o_{h});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]}_{(c)}.$

Let $\mathcal{Q}$ be a minimum core test. Here, for any future $t$, there
exists $\tilde{m}_{t}$ such that
$\mathbb{P}(t\mid\tau_{h})=\langle\tilde{m}_{t},\tilde{\bf
q}_{\tau_{h}}\rangle$ where $[\mathbb{P}(\cdot\mid\tau_{h})]_{|\mathcal{Q}|}$
is a $|\mathcal{Q}|$-dimensional predictive state $\tilde{\bf q}_{\tau_{h}}$.
This satisfies

$\displaystyle\mathbb{P}(o_{h}\mid\tau_{h};a_{h})\tilde{\bf
q}_{\tau_{h},a_{h},o_{h}}=\tilde{M}_{o_{h},a_{h}}\tilde{\bf q}_{\tau_{h}}.$
(23)

where $\tilde{M}_{o_{h},a_{h}}$ is a matrix whose $i$-th row is
$\tilde{m}^{\top}_{o_{h},a_{h}}$ as we see in Section D.

##### Term (c).

We have

$\displaystyle\mathbb{E}[g_{h}(z_{h-1},o_{h})\mid\tau_{h}]$
$\displaystyle={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}\mathbb{E}[[{\textbf{1}}(t=o_{h})]_{t\in{\mathcal{T}}}\mid\tau_{h}]$
$\displaystyle={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}\mathbb{J}_{1}\tilde{\bf
q}_{\tau_{h}}$

where $\mathbb{J}_{1}\in\mathbb{R}^{|{\mathcal{T}}|\times|\mathcal{Q}|}$ is a
matrix whose $i$-th row is $\tilde{m}^{\top}_{t}$. The existence of
$\mathbb{J}_{1}$ is ensured since $\mathcal{Q}$ is a core test.

##### Term (b).

We have

$\displaystyle\mathbb{E}[r_{h}\mid\tau_{h};a_{h}\sim\pi]$
$\displaystyle=\sum_{o_{h},a_{h}}\pi(a_{h}\mid
o_{h},z_{h-1})r_{h}(a_{h},o_{h})\mathbb{P}(o_{h}\mid\tau_{h};a_{h})$
$\displaystyle=\sum_{o_{h},a_{h}}\pi(a_{h}\mid
o_{h},z_{h-1})r_{h}(a_{h},o_{h})\langle\tilde{m}_{o_{h},a_{h}},\tilde{\bf
q}_{\tau_{h}}\rangle$
$\displaystyle={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}^{\pi}_{2}\tilde{\bf
q}_{\tau_{h}}$

for some matrix $\mathbb{J}^{\pi}_{2}$. In the first inequality, we use the
reward is a function of $o_{h},a_{h}$ conditioning on the whole history. From
the first line to the second line, we use a property of core tests.

##### Term (a).

We have

$\displaystyle\mathbb{E}[g_{h+1}(z_{h},o_{h+1})\mid\tau_{h};a_{h}\sim\pi]=\mathbb{E}[{\textbf{1}}(z_{h})^{\top}\mathbb{J}[{\textbf{1}}(t=o_{h+1})]_{t\in{\mathcal{T}}}\mid\tau_{h};a_{h}\sim\pi]$
$\displaystyle=\mathbb{E}[{\textbf{1}}(z_{h})^{\top}\mathbb{J}\mathbb{J}_{3}\tilde{q}_{\tau_{h},a_{h},o_{h}}\mid\tau_{h};a_{h}\sim\pi]$

for some matrix $\mathbb{J}_{3}$. Then, the above is further equal to

$\displaystyle\sum_{a_{h},o_{h}}{\textbf{1}}(z_{h})^{\top}\mathbb{J}\mathbb{J}_{3}\pi(a_{h}\mid
z_{h-1},o_{h})\mathbb{P}(o_{h}\mid\tau_{h};a_{h})\tilde{\bf
q}_{\tau_{h},a_{h},o_{h}}$
$\displaystyle=\sum_{a_{h},o_{h}}{\textbf{1}}(z_{h})^{\top}\mathbb{J}\mathbb{J}_{3}\pi(a_{h}\mid
z_{h-1},o_{h})\tilde{M}_{o_{h},a_{h}}\tilde{\bf q}_{\tau_{h}}$
$\displaystyle={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}^{\pi}_{4}\tilde{\bf
q}_{\tau_{h}}$

for some matrix $\mathbb{J}^{\pi}_{4}$. From the first line to the second
line, we use $\mathbb{P}(o_{h}\mid\tau_{h};a_{h})\tilde{\bf
q}_{\tau_{h},a_{h},o_{h}}=\tilde{M}_{o_{h},a_{h}}\tilde{\bf q}_{\tau_{h}}$ in
(23).

##### Summary.

Combining all terms, there exists a matrix $\mathbb{J}^{\pi}_{5}$ such that

$\displaystyle\mathbb{E}[\\{g_{h+1}(z_{h},o_{h+1})+r_{h}\\}-g_{h}(z_{h-1},o_{h});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}^{\pi}_{5}\mathbb{E}[\tilde{\bf
q}_{\tau_{h}};a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle=\langle\mathrm{Vec}(\mathbb{J}^{\pi}_{5}),{\textbf{1}}(z_{h-1})\otimes\mathbb{E}[\tilde{\bf
q}_{\tau_{h}};a_{1:h-1}\sim\pi^{\prime}]\rangle$

Here, we suppose $\|\mathrm{Vec}(\mathbb{J}^{\pi}_{5})\|\leq\Theta_{W}$ for
any $\pi$. Besides,

$\displaystyle\|{\textbf{1}}(z_{h-1})\otimes\mathbb{E}[\tilde{\bf
q}_{\tau_{h}};a_{1:h-1}\sim\pi^{\prime}]\|_{2}\leq\|\mathbb{E}[\tilde{\bf
q}_{\tau_{h}};a_{1:h-1}\sim\pi^{\prime}]\|_{2}\leq\mathbb{E}[\|\tilde{\bf
q}_{\tau_{h}}\|_{2};a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle\leq\mathbb{E}[\|\tilde{\bf
q}_{\tau_{h}}\|_{1};a_{1:h-1}\sim\pi^{\prime}]=1.$

Thus, we can set $B_{X}=1$.

###  K.3 Sample Complexity

Suppose $\Pi,\mathcal{G}$ are finite and rewards at $h$ lie in $[0,1]$. Assume
the realizability holds. Then,

$\displaystyle\epsilon_{gen}=c\max(\Theta,1)|\mathcal{A}|\sqrt{\ln(|\mathcal{G}_{\max}||\Pi_{\max}|TH/\delta)/m}.$

Following the calculation in Section F, the sample complexity is

$\displaystyle\tilde{O}\left(\frac{|\mathcal{O}|^{2(M-1)}|\mathcal{A}|^{2(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).$

Here, there is no explicit dependence on $|{\mathcal{T}}|$. Note the worst-
case sample complexity of $\ln|\mathcal{G}_{\max}|$ is
$O(|\mathcal{Z}_{h-1}||{\mathcal{T}}|)$ and the worse-case sample complexity
of $\ln|\Pi_{\max}|$ is $O(|\mathcal{Z}_{h-1}||\mathcal{O}||\mathcal{A}|)$.

###  K.4 Most General Case

We consider the general case in Section D. Let $\mathcal{G}_{h}$ be a function
class consisting of $\mathbf{1}(z_{h-1})^{\top}\mathbb{J}_{h}\mathbf{1}(t)$
where $\mathbb{J}_{h}$ satisfies
$\mathbb{J}_{h}\in\mathbb{R}^{\mathcal{Z}_{h-1}\times|{\mathcal{T}}|}$ and
$\|\mathrm{vec}(\mathbb{J}_{h})\|\leq\Theta$. When the realizability holds, we
would get

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

Here, there is no explicit sample complexity of
$|{\mathcal{T}}^{\mathcal{O}}|$. Note the worse-case sample complexity of
$\ln|\mathcal{G}_{\max}|$ is $O(|\mathcal{Z}_{h-1}||{\mathcal{T}}|)$ and the
worst-case sample complexity of $\ln|\Pi_{\max}|$ is
$O(|\mathcal{Z}_{h-1}||\mathcal{O}||\mathcal{A}|)$.

##  Appendix L Proof of Theorem 8

We fix the parameters as in Theorem 8. Let

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

From the assumption, Then, with probability $1-\delta$, we have $\forall
t\in[T],\forall h\in[H]$

$\displaystyle\sup_{\pi\in\Pi,g\in\mathcal{G},f\in\mathcal{F}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g)]-\mathbb{E}[\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g)]]|\leq\epsilon_{gen},$
(24)
$\displaystyle\sup_{g_{1}\in\mathcal{G}_{1}}|\mathbb{E}_{\mathcal{D}^{0}}[g_{1}(o_{1})]-\mathbb{E}[\mathbb{E}_{\mathcal{D}^{0}}[g_{1}(o_{1})]]|\leq\epsilon_{ini}.$
(25)

We first show the following lemma. Recall
$\pi^{\star}=\mathop{\mathrm{argmax}}_{\pi\in\Pi}J(\pi).$

######  Lemma 35 (Optimism).

Set $R:=\epsilon_{gen}$. For all $t\in[T]$, $(\pi^{\star},g^{\pi^{\star}})$ is
a feasible solution of the constrained program. Furthermore, we have
$J(\pi^{\star})\leq\mathbb{E}[g^{t}_{1}(o_{1})]+2\epsilon_{ini}$ for any
$t\in[T]$, where $g^{t}$ is the value link function selected by the algorithm
in iteration $t$.

###### Proof.

For any $\pi$, we have

$\displaystyle\max_{f\in\mathcal{F}_{h}}|\mathbb{E}[\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g^{\pi})]]|=0$

since $g^{\pi}$ is a value link function in $\mathcal{G}$ noting the condition
(c) in Definition 7. Thus,

$\displaystyle\max_{f\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi^{\star},g^{\pi^{\star}})]|\leq\epsilon_{gen}$

using (24) noting $\pi^{\star}\in\Pi,g^{\pi^{\star}}\in\mathcal{G}$. Hence,
$(\pi^{\star},g^{\pi^{\star}})$ is a feasible set for any $t\in[T]$ and any
$h\in[H]$ .

Then, we have

$\displaystyle J(\pi^{\star})$
$\displaystyle=\mathbb{E}[g^{\pi^{\star}}_{1}(o_{1})]\leq\mathbb{E}_{\mathcal{D}^{0}}[g^{\pi^{\star}}_{1}(o_{1})]+\epsilon_{ini}$
(Uniform convergence result)
$\displaystyle\leq\mathbb{E}_{\mathcal{D}^{0}}[g^{t}_{1}(o_{1})]+\epsilon_{ini}$
(Using the construction of algorithm)
$\displaystyle\leq\mathbb{E}[g^{t}_{1}(o_{1})]+2\epsilon_{ini}.$ (Uniform
convergence)

∎

Next, we prove the following lemma to upper bound the per step regret.

######  Lemma 36.

For any $t\in[T]$, we have

$\displaystyle J(\pi^{\star})-J(\hat{\pi})\leq\sum_{h=1}^{H}\left(|\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{t})\rangle|\right)+2\epsilon_{ini}.$

###### Proof.

$\displaystyle J(\pi^{\star})-J(\hat{\pi})$ $\displaystyle\leq
2\epsilon_{ini}+\mathbb{E}[g^{t}_{1}(o_{1})]-J(\pi^{t})$ (From optimism)
$\displaystyle=2\epsilon_{ini}+\sum_{h=1}^{H}\mathbb{E}[g^{t}_{h}(\bar{z}_{h})-\\{r_{h}+g^{t}_{h+1}(\bar{z}_{h+1})\\};a_{1:h}\sim\pi^{t}]$
(Performance difference lemma) $\displaystyle\leq
2\epsilon_{ini}+\sum_{h=1}^{H}|\mathbb{E}[g^{t}_{h}(\bar{z}_{h})-\\{r_{h}+g^{t}_{h+1}(\bar{z}_{h+1})\\};a_{1:h}\sim\pi^{t}]|$
$\displaystyle\leq 2\epsilon_{ini}+\sum_{h=1}^{H}|\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{t})\rangle|.$ (From (a) in Definition 3)

∎

From Lemma 22, we have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=1}^{H}\|X_{h}(\pi^{t})\|_{\Sigma^{-1}_{t,h}}\leq
H\sqrt{\frac{d}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)}.$

######  Lemma 37.

$\displaystyle\|W_{h}(\pi^{t},g^{t})\|^{2}_{\Sigma_{t,h}}\leq 2\lambda
B^{2}_{W}+T\zeta(2\epsilon_{gen}).$

###### Proof.

We have

$\displaystyle\|W_{h}(\pi^{t},g^{t})\|^{2}_{\Sigma_{t,h}}=\lambda\|W_{h}(\pi^{t},g^{t})\|^{2}_{2}+\sum_{\tau=0}^{t-1}\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{\tau})\rangle^{2}.$

The first term is upper-bounded by $\lambda B^{2}_{W}$. The second term is
upper-bounded by

$\displaystyle\sum_{\tau=0}^{t-1}\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{\tau})\rangle^{2}$
$\displaystyle\leq\sum_{k=0}^{t-1}\zeta\left(\max_{f\in\mathcal{F}_{h}}\left|\mathbb{E}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi^{t},g^{t});a_{1:M(h)-1}\sim\pi^{k},a_{M(h):h}\sim\pi^{e}(\pi)]\right|\right)^{2}$
$\displaystyle\leq\sum_{k=0}^{t-1}\zeta\left(\max_{f\in\mathcal{F}_{h}}\left|\mathbb{E}_{\mathcal{D}^{k}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};f,\pi^{t},g^{t})]\right|+\epsilon_{gen}\right)^{2}$
$\displaystyle\leq t\zeta(2\epsilon_{gen})^{2}.$

From the first line to the second line, we use (b) in Definition 7. From the
second line to the third line, we use $\xi$ is a non-decreasing function. In
the last line, we use the constraint on $(\pi^{t},g^{t})$.

∎

Combining lemmas so far, we have

$\displaystyle J(\pi^{\star})-J(\hat{\pi})$
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=1}^{H}|\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{t})\rangle|+2\epsilon_{ini}$
$\displaystyle\leq\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=1}^{H}\|W_{h}(\pi^{t},g^{t})\|_{\Sigma_{t,h}}\|X_{h}(\pi^{t})\|_{\Sigma^{-1}_{t,h}}+2\epsilon_{ini}$
(CS inequality) $\displaystyle\leq H^{1/2}\left[2\lambda
B^{2}_{W}+T\zeta^{2}(2\epsilon_{gen})\right]^{1/2}\left(\frac{dH}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)\right)^{1/2}+2\epsilon_{ini}.$

We set $\lambda$ such that
$B^{2}_{X}/\lambda=B^{2}_{W}B^{2}_{X}/\zeta^{2}(\epsilon_{gen})+1$ and
$T=\left\lceil
2Hd\ln(4Hd(B^{2}_{X}B^{2}_{W}/\zeta^{2}(\tilde{\epsilon}_{gen})+1))\right\rceil$.
Then,

$\displaystyle\frac{Hd}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)$
$\displaystyle\leq\frac{Hd}{T}\ln\left(1+\frac{T}{d}\left(\frac{B^{2}_{W}B^{2}_{X}}{\zeta^{2}(\epsilon_{gen})}+1\right)\right)$
$\displaystyle\leq\frac{Hd}{T}\ln\left(1+\frac{T}{d}\left(\frac{B^{2}_{W}B^{2}_{X}}{\zeta^{2}(\tilde{\epsilon}_{gen})}+1\right)\right)$
$\displaystyle\leq\frac{Hd}{T}\ln\left(\frac{2T}{d}\left(\frac{B^{2}_{W}B^{2}_{X}}{\zeta^{2}(\tilde{\epsilon}_{gen})}+1\right)\right)\leq
1$

since $a\ln(bT)/T\leq 1$ when $T=2a\ln(2ab)$.

Finally, the following holds

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

##  Appendix M Sample Complexity in $M$-step Decodable POMDPs

We first give a summary of our results. Then, we show that an $M$-step
decodable POMDP is a PO-bilinear rank model. After showing the uniform
convergence of the loss function with fast rates, we calculate the sample
complexity. Since we use squared loss functions, we need to modify the proof
of Theorem 1.

###  M.1 PO-bilinear Rank Decomposition (Proof of Lemma 10)

In this section, we derive the PO-bilinear decomposition of $M$-step decodable
POMDPs (Lemma 10 ).

First, we define moment matching policies following [efroni2022provable]. We
denote $M(h)=h-M$.

######  Definition 10 (Moment Matching Policies).

For $h^{\prime}\in[M(h),h]$, we define

$\displaystyle
x_{h^{\prime}}=(s_{M(h):{h^{\prime}}},o_{M(h):{h^{\prime}}},a_{M(h):h^{\prime}-1})\in\mathcal{X}_{l}$

where $\mathcal{X}_{l}=S^{l}\times\mathcal{O}^{l}\times\mathcal{A}^{l-1}$ and
$l=h^{\prime}-M(h)+1$. For an $M$-step policy $\pi$ and $h\in[H]$, we define
the moment matching policy
$\mu^{\pi,h}=\\{\mu^{\pi,h}_{h^{\prime}}:\mathcal{X}_{h^{\prime}-M(h)+1}\to\Delta(\mathcal{A})\\}^{h-1}_{h^{\prime}=M(h)}$:

$\displaystyle\mu^{\pi,h}_{h^{\prime}}(a_{h^{\prime}}\mid
x_{h^{\prime}}):=\mathbb{E}[\pi_{h^{\prime}}(a_{h^{\prime}}\mid\bar{z}_{h^{\prime}})\mid
x_{h^{\prime}};\pi].$

Note the expectation in the right hand side is taken under a policy $\pi$.

Using [efroni2022provable, Lemma B.2], we have

$\displaystyle\mathrm{Br}(\pi,g;\pi^{\prime})$
$\displaystyle=\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\pi]$
$\displaystyle=\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\pi]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}\mid
s_{M(h)};a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\pi];a_{1:M(h)-1}\sim\pi^{\prime}]$
$\displaystyle=\left\langle X_{h}(\pi^{\prime}),W_{h}(\pi,g)\right\rangle.$

where

$\displaystyle W_{h}(\pi,g)$
$\displaystyle=\int\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}\mid
s_{M(h)};a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\pi]\mu(s_{M(h)})\mathrm{d}(s_{M(h)}),$
$\displaystyle X_{h}(\pi^{\prime})$
$\displaystyle=\mathbb{E}[\phi(s_{M(h)-1},a_{M(h)-1});a_{1:M(h)-1}\sim\pi^{\prime}].$

Thus, the first condition in Definition 7 ((6)) is satisfied

Next, we show the second condition in Definition 7 ((7)). This is proved as
follows

$\displaystyle\frac{0.5}{|\mathcal{A}|^{M}}\left\langle
X_{h}(\pi^{\prime}),W_{h}(\pi,g)\right\rangle^{2}$ (26)
$\displaystyle=\frac{0.5}{|\mathcal{A}|^{M}}\left(\mathbb{E}\left[\left(g_{h}(\bar{z}_{h})-(\mathcal{B}^{\pi}_{h}g_{h+1})(\bar{z}_{h})\right);a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h}\right]\right)^{2}$
$\displaystyle\leq\frac{0.5}{|\mathcal{A}|^{M}}\mathbb{E}\left[\left(g_{h}(\bar{z}_{h})-(\mathcal{B}^{\pi}_{h}g_{h+1})(\bar{z}_{h})\right)^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h}\right]$
(Jensen’s inequality)
$\displaystyle\leq\frac{1}{|\mathcal{A}|^{M}}\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[\left(g_{h}(\bar{z}_{h})-(\mathcal{B}^{\pi}_{h}g_{h+1})(\bar{z}_{h})\right)f(\bar{z}_{h})-0.5f(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h}\right]$
$\displaystyle=\frac{1}{|\mathcal{A}|^{M}}\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[|\mathcal{A}|\pi_{h}(a_{h}|\bar{z}_{h})\left(g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\right)f(\bar{z}_{h})-0.5f(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\mathcal{U}(\mathcal{A})\right]$
$\displaystyle\leq\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[|\mathcal{A}|\pi_{h}(a_{h}|\bar{z}_{h})\left(g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\right)f(\bar{z}_{h})-0.5f(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\mathcal{U}(\mathcal{A})\right]$
$\displaystyle=\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[l_{h}(\bar{z}_{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].$
(27)

From the first line to the second line, we use [efroni2022provable, Lemma
B.2]. From the third to the fourth line, we use the Bellman completeness
assumption:
$-(\mathcal{B}^{\pi}_{h}\mathcal{G})+\mathcal{G}_{h}\subset\mathcal{F}_{h}$.
From the fourth line to the fifth line, we use importance sampling.

Finally, we show the third condition in Definition 7 (8):

$\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.$
(28)

This follows since

$\displaystyle\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})]$
$\displaystyle=\mathbb{E}\left[|\mathcal{A}|\pi_{h}(a_{h}|\bar{z}_{h})\left(g^{\pi}_{h}(\bar{z}_{h})-r_{h}-g^{\pi}_{h+1}(\bar{z}_{h+1})\right)f(\bar{z}_{h})-0.5f(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\mathcal{U}(\mathcal{A})\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}[|\mathcal{A}|\pi_{h}(a_{h}|\bar{z}_{h})\left(g^{\pi}_{h}(\bar{z}_{h})-r_{h}-g^{\pi}_{h+1}(\bar{z}_{h+1})\right)\mid\bar{z}_{h}]f(\bar{z}_{h})-0.5f(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\mathcal{U}(\mathcal{A})\right]$
$\displaystyle=\mathbb{E}\left[-0.5f(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\mathcal{U}(\mathcal{A})\right].$

###  M.2 Uniform Convergence

We define the operator

$\displaystyle(\mathcal{B}^{\pi}_{h}g)(\bar{z}_{h}):=\mathbb{E}[r_{h}+g_{h+1}(\bar{z}_{h+1})\mid\bar{z}_{h};a_{h}\sim\pi].$

and

$\displaystyle(\bar{\mathcal{B}}^{\pi}_{h}g)(\bar{z}_{h}):=-(\mathcal{B}^{\pi}_{h}g)(\bar{z}_{h})+g_{h}.$

######  Lemma 38 (Uniform Convergence).

Let $|\mathcal{D}|=m$. Suppose $\|\mathcal{F}_{h}\|_{\infty}\leq 3H$ for
$h\in[H]$. Fix $\pi^{\prime}\in\Pi$.

  1. 1.

Take a true link function $g^{\pi}\in\mathcal{G}$. Then, it satisfies

$\displaystyle\max_{f_{h}\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}}[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{g^{\pi}_{h}(\bar{z}_{h})-r_{h}-g^{\pi}_{h+1}(\bar{z}_{h+1})\\}f_{h}(\bar{z}_{h})-0.5f_{h}(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim
U(\mathcal{A})]$ $\displaystyle\leq
c_{1}\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|/\delta)}{m}.$

  2. 2.

Suppose $g(\pi)$ satisfies

$\displaystyle\max_{f_{h}\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}}[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{g_{h}(\pi)(\bar{z}_{h})-r_{h}-g_{h+1}(\pi)(\bar{z}_{h+1})\\}f_{h}(\bar{z}_{h})-0.5f_{h}(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim
U(\mathcal{A})]|$ $\displaystyle\leq\Lambda,$

and the Bellman completeness
$\bar{\mathcal{B}}^{\pi}_{h}\mathcal{G}\subset\mathcal{F}_{h}(\forall\pi\in\Pi)$
holds. Then, with probability $1-\delta$, we have

$\displaystyle\mathbb{E}[(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h});a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim
U(\mathcal{A})]$
$\displaystyle\leq\Lambda+c_{2}\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|/\delta)}{m}.$

###### Proof.

To simplify the notation, we define

$\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)=\pi_{h}(a_{h}\mid\bar{z}_{h})|\mathcal{A}|\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}.$

Given $g\in\mathcal{G}$, we define $\hat{f}_{h}(\cdot;g)$ as the maximizer:

$\displaystyle\mathop{\mathrm{argmax}}_{f_{h}\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}}[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}f_{h}(\bar{z}_{h})-0.5f_{h}(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim
U(\mathcal{A})]|.$

In this proof, the expectation is always taken for the data generating process
$\mathcal{D}$. We first observe

$\displaystyle\mathbb{E}_{\mathcal{D}}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)f_{h}(\bar{z}_{h})-0.5f_{h}(\bar{z}_{h})^{2}]$
$\displaystyle=0.5\mathbb{E}_{\mathcal{D}}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)^{2}-\\{\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)-f_{h}(\bar{z}_{h})\\}^{2}].$

Then, we define

$\displaystyle\mathrm{Er}_{h}(f,g):=0.5\\{\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)-f_{h}(\bar{z}_{h})\\}^{2}-0.5\\{\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)-(\bar{\mathcal{B}}^{\pi}_{h}g)(\bar{z}_{h})\\}^{2}].$

As the first step, we prove with probability $1-\delta$

$\displaystyle\forall
g;|\mathbb{E}_{\mathcal{D}}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]|\leq\frac{12H|\mathcal{A}|\ln(2|\mathcal{F}_{h}|||\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}.$
(29)

We first fix $g$. Then, from the definition of $\hat{f}_{h}(\cdot;g)$ and the
Bellman completeness
$\bar{\mathcal{B}}^{\pi}_{h}\mathcal{G}\subset\mathcal{F}_{h}$, we have

$\displaystyle\mathbb{E}_{\mathcal{D}}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]\leq
0.$ (30)

Here, we invoke Bernstein’s inequality:

$\displaystyle\forall
f\in\mathcal{F}_{h};|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})\mathrm{Er}_{h}(f,g))|\leq\sqrt{\mathbb{E}[\mathrm{Er}_{h}(f,g)]\frac{\ln(2|\mathcal{F}_{h}|/\delta)}{m}}+\frac{(6H|\mathcal{A}|)^{2}\ln(2|\mathcal{F}_{h}|/\delta)}{m}.$
(31)

Hereafter, we condition on the above event. Then, combining (30) and (31), we
have

$\displaystyle\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]$
$\displaystyle\leq\mathbb{E}_{\mathcal{D}}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]+|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)|$
$\displaystyle\leq\sqrt{\frac{\mathbb{E}[\mathrm{Er}^{2}_{h}(\hat{f}_{h}(\cdot;g),g)]\ln(2|\mathcal{F}_{h}|/\delta)(6H|\mathcal{A}|)^{2}}{m}}+\frac{(6H|\mathcal{A}|)^{2}\ln(2|\mathcal{F}_{h}|/\delta)}{m}.$

Here, we use

$\displaystyle\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]$
$\displaystyle=0.5\mathbb{E}[\\{f_{h}(\bar{z}_{h})-(\bar{\mathcal{B}}^{\pi}_{h}g)(\bar{z}_{h})\\}^{2}],$
$\displaystyle\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)^{2}]$
$\displaystyle\leq\mathbb{E}[\\{f_{h}(\bar{z}_{h})-(\bar{\mathcal{B}}^{\pi}_{h}g)(\bar{z}_{h})\\}^{2}](6H|\mathcal{A}|)^{2}=\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g))](6H|\mathcal{A}|)^{2}.$

Thus, by some algebra,

$\displaystyle\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]\leq\frac{(12H|\mathcal{A}|)^{2}\ln(2|\mathcal{F}_{h}|/\delta)}{m}.$

Besides,

$\displaystyle|\mathbb{E}_{\mathcal{D}}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]|$
$\displaystyle\leq\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g))]+|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]|$
$\displaystyle\leq\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)]+\sqrt{\frac{\mathbb{E}[\mathrm{Er}_{h}(\hat{f}_{h}(\cdot;g),g)](6H|\mathcal{A}|)^{2}\ln(2|\mathcal{F}_{h}|/\delta)}{m}}+\frac{(6H|\mathcal{A}|)^{2}\ln(2|\mathcal{F}_{h}|/\delta)}{m}$
$\displaystyle\leq\frac{3(12H|\mathcal{A}|)^{2}\ln(2|\mathcal{F}_{h}|/\delta)}{m}+\frac{27H|\mathcal{A}|\ln(2|\mathcal{F}_{h}|/\delta)}{m}.$

Lastly, by union bounds over $\mathcal{G}_{h},\mathcal{G}_{h+1}$, the
statement (29) is proved. Note $\bar{\mathcal{B}}^{\pi}_{h}g^{\pi}=0$.

##### First Statement.

$\displaystyle|\mathbb{E}_{\mathcal{D}}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g^{\pi})\hat{f}_{h}(\bar{z}_{h};g^{\pi})-0.5\hat{f}_{h}(\bar{z}_{h};g^{\pi})^{2}]|$
$\displaystyle=|0.5\mathbb{E}_{\mathcal{D}}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g^{\pi})]-0.5\mathbb{E}_{\mathcal{D}}[\\{\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g^{\pi})-f_{h}(\bar{z}_{h})\\}^{2}]|$
$\displaystyle\leq
c\frac{H|\mathcal{A}|\ln(|\mathcal{F}_{h}|\mathcal{G}_{h}||\mathcal{G}_{h+1}/\delta)}{m}.$

From the second line to the third line, we use (29).

##### Second Statement.

Now, we use the assumption on $g(\pi)$:

$\displaystyle\mathbb{E}_{\mathcal{D}}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g(\pi))\hat{f}_{h}(\bar{z}_{h};g(\pi))-0.5\hat{f}_{h}(\bar{z}_{h};g(\pi))^{2}]\leq\Lambda.$

From what we showed in (29), this implies

$\displaystyle\mathbb{E}_{\mathcal{D}}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g(\pi))(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))(\bar{z}_{h})-0.5(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]\leq\Lambda+\frac{3(12H|\mathcal{A}|)^{2}\ln(|\mathcal{F}_{h}||\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}.$

Recall we want to upper-bound the error for
$\mathbb{E}[0.5(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})].$ Here,
we use the following observation later:

$\displaystyle\mathbb{E}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g(\pi))(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))(\bar{z}_{h})-0.5(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]=\mathbb{E}[0.5(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})].$

We use Bernstein’s inequality: with probability $1-\delta$, for any
$g\in\mathcal{G}$,

$\displaystyle|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)(\mathcal{B}^{\pi}_{h}g)(\bar{z}_{h})-0.5(\mathcal{B}^{\pi}_{h}g)^{2}(\bar{z}_{h})]|$
$\displaystyle\leq\sqrt{\frac{\mathbb{E}[(3|\mathcal{A}|H)^{2}(\mathcal{B}^{\pi}_{h}g)^{2}(\bar{z}_{h})]\ln(2|\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}}+\frac{(3|\mathcal{A}|H)^{2}\ln(|\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}.$

Here, we use

$\displaystyle\mathbb{E}[\\{\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)(\mathcal{B}^{\pi}_{h}g)(\bar{z}_{h})-0.5(\mathcal{B}^{\pi}_{h}g)^{2}(\bar{z}_{h})\\}^{2}]$
$\displaystyle\leq\mathbb{E}[\\{\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g)(\mathcal{B}^{\pi}_{h}g)(\bar{z}_{h})-0.5(\mathcal{B}^{\pi}_{h}g)^{2}(\bar{z}_{h})\\}](6|\mathcal{A}|H)^{2}.$

Hereafter, we condition on the above event.

Finally, we have

$\displaystyle\mathbb{E}[0.5(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]$
$\displaystyle\leq\mathbb{E}_{\mathcal{D}}[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g(\pi))(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))(\bar{z}_{h})-0.5(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]+$
$\displaystyle+|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g(\pi))(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))(\bar{z}_{h})-0.5(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]|$
$\displaystyle\leq\Lambda+\frac{3(12H|\mathcal{A}|)^{2}\ln(4|\mathcal{F}_{h}||\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}$
$\displaystyle+|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\alpha_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};g(\pi))(\mathcal{B}^{\pi}_{h}g(\pi))(\bar{z}_{h})-0.5(\mathcal{B}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]|$
$\displaystyle\leq\Lambda+\frac{3(12H|\mathcal{A}|)^{2}\ln(4|\mathcal{F}_{h}||\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}+\sqrt{\frac{\mathbb{E}[0.5(\mathcal{B}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]\ln(4|\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}}+\frac{\ln(|\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}.$

Hence,

$\displaystyle\forall\pi\in\Pi,\forall
g(\pi);\mathbb{E}[0.5(\mathcal{B}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h})]\leq\Lambda+c\frac{(H|\mathcal{A}|)^{2}\ln(|\mathcal{F}_{h}||\mathcal{G}_{h}||\mathcal{G}_{h+1}|/\delta)}{m}.$

∎

###  M.3 Proof of Main Statement

We define

$\displaystyle|\mathcal{F}_{\max}|=\max_{h\in[H]}|\mathcal{F}_{h}|,\,|\Pi_{\max}|=\max_{h\in[H]}|\Pi_{h}|,|\mathcal{G}_{\max}|=\max_{h\in[H]}|\mathcal{G}_{h}|.$

Let

$\displaystyle\epsilon^{2}_{gen}$
$\displaystyle=c_{1}\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|T(H+1)/\delta)}{m},$
$\displaystyle\tilde{\epsilon}^{2}_{gen}$
$\displaystyle=c_{1}\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|(H+1)/\delta)}{m},$
$\displaystyle\epsilon_{ini}$
$\displaystyle=c_{3}\sqrt{\frac{(H|\mathcal{A}|)^{2}\ln(|\mathcal{G}_{1}|T(H+1)/\delta)}{m}},$
$\displaystyle T$
$\displaystyle=2Hd\ln\left(4Hd\left(\frac{B^{2}_{X}B^{2}_{W}}{\tilde{\epsilon}_{gen}}+1\right)\right),\quad
R=\epsilon^{2}_{gen}.$

Then, from the first statement in Lemma 38, with probability $1-\delta$,
$\forall t\in[T],\forall h\in[H],\forall\pi\in\Pi$

$\displaystyle\max_{f_{h}\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{g^{\pi}_{h}(\bar{z}_{h})-r_{h}-g^{\pi}_{h+1}(\bar{z}_{h+1})\\}f_{h}(\bar{z}_{h})-0.5f_{h}(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{t},a_{M(h):h}\sim
U(\mathcal{A})]|$ (32) $\displaystyle\leq
c_{1}\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|T(H+1)/\delta)}{m}.$

Besides, from the second statement in Lemma 38, for $\pi\in\Pi,\forall
t\in[T],\forall h\in[H]$, when $g(\pi)$ satisfies

$\displaystyle\max_{f_{h}\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}[|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\\{g_{h}(\pi)(\bar{z}_{h})-r_{h}-g_{h+1}(\pi)(\bar{z}_{h+1})\\}f_{h}(\bar{z}_{h})-0.5f_{h}(\bar{z}_{h})^{2};a_{1:M(h)-1}\sim\pi^{t},a_{M(h):h}\sim
U(\mathcal{A})]|$ $\displaystyle\leq
c_{1}\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|T(H+1)/\delta)}{m},$

we have

$\displaystyle\mathbb{E}[(\bar{\mathcal{B}}^{\pi}_{h}g(\pi))^{2}(\bar{z}_{h});a_{1:M(h)-1}\sim\pi^{t},a_{M(h):h-1}\sim
U(\mathcal{A})]\leq(c_{1}+c_{2})\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|TH/\delta)}{m}.$
(33)

We first show the optimism. Recall
$\pi^{\star}=\mathop{\mathrm{argmax}}_{\pi\in\Pi}J(\pi).$

######  Lemma 39 (Optimism).

Set $R=\epsilon^{2}_{gen}$. For all $t\in[T]$, $(\pi^{\star},g^{\pi^{\star}})$
is a feasible solution of the constrained program. Furthermore, we have
$J(\pi^{\star})\leq\mathbb{E}[g^{t}_{1}(o_{1})]+2\epsilon_{ini}$ for any
$t\in[T]$.

###### Proof.

For any $\pi\in\Pi$, letting $g^{\pi}\in\mathcal{G}$ be a corresponding value
link function, we have

$\displaystyle\max_{f\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};f,\pi,g^{\pi})]|\leq\epsilon^{2}_{gen}.$

using (32). This implies

$\forall t\in[T],\forall
h\in[H],\max_{f\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};f,\pi^{\star},g^{\pi^{\star}})]|\leq\epsilon^{2}_{gen}.$

Hence, $(\pi^{\star},g^{\pi^{\star}})$ is a feasible set for any $t\in[T]$.
Then, we have

$\displaystyle J(\pi^{\star})$
$\displaystyle=\mathbb{E}[g^{\pi^{\star}}_{1}(o_{1})]\leq\mathbb{E}_{\mathcal{D}^{t}_{1}}[g^{\pi^{\star}}_{1}(o_{1})]+\epsilon_{ini}$
$\displaystyle\leq\mathbb{E}_{\mathcal{D}^{t}_{1}}[g^{t}_{1}(o_{1})]+\epsilon_{ini}\leq\mathbb{E}[g^{t}_{1}(o_{1})]+2\epsilon_{ini}.$

∎

Next, recall the following two statements. The following statements are proved
as before in the proof of Theorem 1.

  * •

For any $t\in[T]$,

$\displaystyle J(\pi^{\star})-J(\pi^{t})\leq\sum_{h=1}^{H}|\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{t})\rangle|+2\epsilon_{ini}.$

  * •

Let $\Sigma_{t,h}=\lambda
I+\sum_{\tau=0}^{t-1}X_{h}(\pi^{\tau})X_{h}(\pi^{\tau})^{\top}$. We have

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\sum_{h=1}^{H}\|X_{h}(\pi^{t})\|^{2}_{\Sigma^{-1}_{t,h}}\leq
H\sqrt{\frac{d}{T}\ln\left(1+\frac{TB^{2}_{X}}{d\lambda}\right)}.$

######  Lemma 40.

$\displaystyle\|W_{h}(\pi^{t},g^{t})\|^{2}_{\Sigma_{t,h}}\leq 2\lambda
B^{2}_{W}+T|\mathcal{A}|^{M}\epsilon^{2}_{gen}.$

###### Proof.

We have

$\displaystyle\|W_{h}(\pi^{t},g^{t})\|^{2}_{\Sigma_{t,h}}=\lambda\|W_{h}(\pi^{t},g^{t})\|^{2}_{2}+\sum_{\tau=0}^{t-1}\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{\tau})\rangle^{2}.$

The first term is upper-bounded by $\lambda B^{2}_{W}$. The second term is
upper-bounded by

$\displaystyle\sum_{\tau=0}^{t-1}\langle
W_{h}(\pi^{t},g^{t}),X_{h}(\pi^{\tau})\rangle^{2}$
$\displaystyle\leq|\mathcal{A}|^{M}\sum_{\tau=0}^{t-1}\mathbb{E}[\mathbb{E}[|\mathcal{A}|\pi^{t}_{h}(a_{h}\mid\bar{z}_{h})g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\mid\bar{z}_{h};a_{h}\sim
U(\mathcal{A})]^{2};a_{1:M(h)-1}\sim\pi^{\tau},a_{M(h):h-1}\sim
U(\mathcal{A})]$
$\displaystyle=|\mathcal{A}|^{M}\sum_{\tau=0}^{t-1}\mathbb{E}[(\bar{\mathcal{B}}^{\pi^{t}}_{h}g(\pi))^{2}(\bar{z}_{h});a_{1:M(h)-1}\sim\pi^{\tau},a_{M(h):h-1}\sim
U(\mathcal{A})]$
$\displaystyle\leq|\mathcal{A}|^{M}T(c_{1}+c_{2})\frac{(H|\mathcal{A}|)^{2}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|TH/\delta)}{m}\leq
T|\mathcal{A}|^{M}\epsilon^{2}_{gen}.$

From the first line to the second line, we use (26). Here, from the third line
to the fourth line, we use (33). ∎

The rest of the argument is the same as the proof in Theorem 1. Finally, the
following holds

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

##### Sample Complexity Result.

We want to find $m$ such that

$\displaystyle\sqrt{\frac{H^{2}|\mathcal{A}|^{2+M}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|TH/\delta)}{m}}[H^{2}d\ln(HdB^{2}_{X}B^{2}_{W}m)]^{1/2}\leq\epsilon.$

where

$\displaystyle T=Hd\ln(HdB^{2}_{X}B^{2}_{W}m).$

By organizing terms, we have

$\displaystyle\sqrt{\frac{H^{4}d|\mathcal{A}|^{2+M}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|Hd/\delta)\ln(HdB^{2}_{X}B^{2}_{W}m)}{m}}\leq\epsilon.$

Thus, setting the following $m$ is enough:

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

The total sample we use $mTH$ is

$\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).$

##  Appendix N Sample Complexity in Observable POMDPs with Latent Low-rank
Transition

This section largely follows the one in Section M.

###  N.1 Existence of Value Link Functions

Since we consider the discrete setting, we can set the value link function
class as Section H. Hence, we set

$\displaystyle\mathcal{G}_{h}=\left\\{\langle\theta,\mathbf{1}(z)\otimes\mathbb{O}^{\dagger}\mathbf{1}(o)\rangle;\|\theta\|_{\infty}\leq
H\right\\}.$

Then, we can ensure $\|\mathcal{G}_{h}\|\leq H/\sigma_{1}$. Then, from the
construction of $\mathcal{F}_{h}$, we can also ensure $\|\mathcal{F}_{h}\|\leq
4H/\sigma_{1}$.

###  N.2 PO-bilinear Rank Decomposition (Proof of Lemma 11)

In this section, we derive the PO-bilinear decomposition of observable POMDPs
with the latent low-rank transition. We want to prove Lemma 11. Recall
$M(h)=\max(h-M,1)$.

Using [efroni2022provable, Lemma B.2], we have

$\displaystyle\mathrm{Br}(\pi,g;\pi^{\prime})=\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\pi]$
$\displaystyle=\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\pi]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}\mid
s_{M(h)};a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\pi];a_{1:M(h)-1}\sim\pi^{\prime}]$
$\displaystyle=\left\langle X_{h}(\pi^{\prime}),W_{h}(\pi,g)\right\rangle$

where

$\displaystyle W_{h}(\pi,g)$
$\displaystyle=\int\mathbb{E}[\\{g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\\}\mid
s_{M(h)};a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\pi]\mu(s_{M(h)})\mathrm{d}(s_{M(h)}),$
$\displaystyle X_{h}(\pi^{\prime})$
$\displaystyle=\mathbb{E}[\phi(s_{M(h)-1},a_{M(h)-1});a_{1:M(h)-1}\sim\pi^{\prime}].$

Thus, the first condition in Definition 7 is satisfied

Next, we show the second condition in Definition 7. This is proved as follows:

$\displaystyle\frac{0.5}{|\mathcal{A}|^{M}}\left\langle
X_{h}(\pi^{\prime}),W_{h}(\pi,g)\right\rangle^{2}$
$\displaystyle=\frac{0.5}{|\mathcal{A}|^{M}}\mathbb{E}\left[\left(g_{h}(\bar{z}_{h})-(\mathcal{B}^{\pi}_{h}g_{h+1})(\tau_{h})\right);a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h}\right]^{2}$
$\displaystyle\leq\frac{0.5}{|\mathcal{A}|^{M}}\mathbb{E}\left[\left(g_{h}(\bar{z}_{h})-(\mathcal{B}^{\pi}_{h}g_{h+1})(\tau_{h})\right)^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h}\right]$
$\displaystyle\leq\frac{1}{|\mathcal{A}|^{M}}\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[\left(g_{h}(\bar{z}_{h})-(\mathcal{B}^{\pi}_{h}g_{h+1})(\tau_{h})\right)f(\tau_{h})-0.5f(\tau_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h}\right]$
$\displaystyle=\frac{1}{|\mathcal{A}|^{M}}\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[|\mathcal{A}|\pi_{h}(a_{h}|\bar{z}_{h})\left(g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\right)f(\tau_{h})-0.5f(\tau_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h-1}\sim\mu^{\pi,h},a_{h}\sim\mathcal{U}(\mathcal{A})\right]$
$\displaystyle\leq\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[|\mathcal{A}|\pi_{h}(a_{h}|\bar{z}_{h})\left(g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1})\right)f(\tau_{h})-0.5f(\tau_{h})^{2};a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\mathcal{U}(\mathcal{A})\right]$
$\displaystyle=\max_{f\in\mathcal{F}_{h}}\mathbb{E}\left[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].$

From the first line to the second line, we use [efroni2022provable, Lemma
B.2]. From the third to the fourth line, we use the Bellman completeness
assumption:
$-(\mathcal{B}^{\pi}_{h}\mathcal{G})+\mathcal{G}_{h}\subset\mathcal{F}_{h}$.
From the fourth line to the fifth line, we use importance sampling.

The third condition

$\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
U(\mathcal{A})]\right\rvert=0.$

is easily proved.

Finally, the following norm constraints hold:

$\displaystyle\|W_{h}(\pi,g)\|\leq
3C_{\mathcal{G}}\sqrt{d},\quad\|X_{h}(\pi^{\prime})\|\leq 1.$

##### Sample Complexity Result.

Following the same procedure as Section M, here, we want to find $m$ such that