Spectral Learning for Infinite-Horizon Average-Reward POMDPs
Authors: Alessio Russo
Alberto Maria Metelli
Marcello Restelli
Venue: NeurIPS 2025 poster ()
Keywords: Infinite-Horizon
Average-Reward POMDPs
Spectral Learning
Regret Minimization
Primary area: reinforcement_learning

Abstract: We address the learning problem in the context of infinite-horizon average-reward POMDPs. Traditionally, this problem has been approached using $\textit{Spectral Decomposition}$ (SD) methods applied to samples collected under non-adaptive policies, such as uniform or round-robin policies. Recently, SD techniques have been extended to accommodate a restricted class of adaptive policies such as $\textit{memoryless policies}$. However, the use of adaptive policies has introduced challenges related to data inefficiency, as SD methods typically require all samples to be drawn from a single policy.
In this work, we propose $\texttt{Mixed Spectral Estimation}$, which generalizes spectral estimation techniques to support a broader class of $\textit{belief-based policies}$. We solve the open question of whether spectral methods can be applied to samples collected from multiple policies, and we provide finite-sample guarantees for our approach under standard observability and ergodicity assumptions.
Building on this data-efficient estimation method, we introduce the $\texttt{Mixed Spectral UCRL}$ algorithm. Through a refined theoretical analysis, we demonstrate that it achieves a regret bound of $\widetilde{\mathcal{O}}(\sqrt{T})$ when compared to the optimal policy, without requiring full knowledge of either the transition or the observation model. Finally, we present numerical simulations that validate the theoretical analysis of both the proposed estimation procedure and the $\texttt{Mixed Spectral UCRL}$ algorithm.

Spectral Learning for Infinite-Hoiizon Everage-Reward POMDPs
Alessio Russo
Alberto Maria Metelli
DEIB, Politecnico di Milano
DEIB, Politecnico di Milano
alessio. russo@polimi..... it
albertomaria wtt.:/aaraaammmeeeoooo.loll...a.
Marcello Restelli
DEIB, Politecnico di Milano
marcello rerteello.esttellieooo.....
Abstract
We address the learning problem in the context of infinite-horizon average-reward POMDPs. Traditionally, this problem has been approached using Spectral Decom- position (SD) methods applied to samples collected under non-adaptive policies, such as uniform or round-robin policies. Recently, SD techniques have been ex- tended to accommodate a restricted class of adaptive policies such as memoryless policies. However, the use of adaptive policies has introduced challenges related data inefficiency, SD methods typically require all samples to be drawn from single policy. In this work, we propose Mixed Spectral Estimati oon, which generalizes spectral estimation techniques to support broader class of belief-based policies. We solve the open question of whether spectral methods can be applied samples collected from multiple policies, and we provide finite-sample guarantees for our approach under standard observability and ergodicity assumptions. Building this data-efficient estimation method, we introduce the Mixed Spectral UCRL algorithm. Through a refined theoretical analysis, we demonstrate that it achieves a regret bound of ((VT) when compared to the optimal policy, without requiring full knowledge of either the transition the observation model. Finally, we present numerical simulations that validate the theoretical analysis of both the proposed estimation procedure and the Mixed Spectral UCRL algorithm.
Introduction
In Reinforcement Learning (RL) 311 an agent interacts with an unknown partially known environment to maximize the long-term sum of rewards. This approach has been successfully used in a variety of problems [23 28 under the assumption of fully observing the state of the environment. However, less attention has been paid to the more realistic scenario where the agent only receives partial and noisy observations from the environment, problem which can be modeled through the Partially Observable Markov Decision Process (POMDP) 35 formalism. This setting can be used to represent various real-world applications such autonomous driving 18), resource allocation 77] or financial settings (6] Dealing with POMDPs is notably challenging task both (i) statistically since it requires estimating the latent model parameters, and (ii) computationally since computing the optimal policy for a POMDP is intractable even when the model parameters are known 244.
In this work, we tackle the anfinite-horizon average-reward POMDP formulation. In the past works, the learning problem in this setting has been addressed using Spectral Decomposition (SD) methods [1 In particular, the standard approach consists of deploying fully explorative policies (e.g.. round- robin or uniform) for data collection and then leveraging SD techniques for subsequent model
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(2). A different approach is proposed in 3 where spectral strategies are extended to samples collected from adaptive memoryless policies However, the model estimation they propose requires all samples to be drawn from a unique policy, which introduces data inefficiency issues since samples collected with older policies cannot be reused for model estimation. In addition, their approach is limited to stochastic policies under which each action can be chosen with a minimum positive probability& > O. By inspecting the limitations of current works, an important question arises: Can we apply spectral techniques on samples collected from multiple adaptive policies to improve the sample-efticiency of online learning algorithms for POMDPs?
estimation [1]
Contributions. In this paper, we address this question and we provide the following contributions:
We extend the spectral estimation procedure to the larger class of stationary belief- belief-based policies.
We answer the previous question affirmatively and propose procedure, Mixed Spectral Estimation, with finite-sample guarantees for estimating the POMDP parameters (Section 5
We plug this novel estimation approach into a regret minimization algorithm, Mixed Spectral UCRL, and we show that we can indeed avoid using stochastic policies required in previous works. By focusing on instances satisfying the common one-step reachability assumption (Assump- tion 6.1p, our algorithm is the first to achieve a regret of order Ö competing against the optimal belief- policy, hence improving over the state-of the--therrrr regret of order ((T2/33 (Section()) 6).
We provide numerical simulations showing both the effectiveness of the estimation procedure and the performance of our Mixed Spectral UCRL algorithm (Section 7
2 Preliminaries
In this section, we provide the necessary background for the subsequent discussion. In the following, we will use (x)) to denote the simplex over finite set X, (x( to denote the S-th singular value of matrix X. and xt to denote its Moore-Penrose pscudo-inverse.
Partially Observable MDP. A Partially Observable Markov Decision Process (POMDP) (55 is defined by a tuple Q == (S, O, T, O, r) with S being a finite state space (S = [S), A a finite
action space (A == (A) and O a finite observation space (O = 101). T (Ta Jae denotes collection of transition matrices To E R R for every E A. Each transition matrix [-(- E A(S) defines the distribution of the next state when the agent takes action a in state 8 S. 0 E ROx5
denotes the observation matrix (-1ss) E A(O) that represents the distribution over observations when the agent is in state s. / E (S)) denotes the distribution over the initial state, while r O [o. 1] is the known reward function, mapping each observation to a finite reward such that r(o) is the reward received when the agents observe o O. In a POMDP, states are hidden and the agent can only see its own actions and the observations. At each step t E N, the agent is in an unknown state 8,, it receives an observation og determined by O(-|s)) and reward r(o:). then chooses an action a and the environment transitions into a new state $1+1 according to Ta, (-1st). Then, the process repeats.
Policies in POMDPs. A policy == (Tr) a sequence of decision rules prescribing the action to play. We use Hi, == (O x A)t-1 x O to denote the space of histories up to time 1. A deterministic policy Te : Hl A is such that (h) A is the action chosen when history h H4 is observed.
From POMDP to Belief MDP. When the observation and the transition models are known, it is possible to build a belief vector b, E B (with B = A(S)) from the observed history he := (oj, a + o,, where @ denotes the sequence concatenation operator, as be(s) := Pr(s; s) s)he), representing the probability that the true state is s having observed history h4. The update rule of the belief b, is determined using Bayes' theorem as:
Eves ((or)))Ta, (618')b,-1s5))
(e(s) = Ev.wes O(orls))Ta, (8'|s")be-1(s"
(I)
By using this notion of belief, we can transform the POMDP into a belief MDP [17] (which is continuous-state MDP even the original POMDP is tabular), which used to address the POMDP
Under a memoryless policy, the choice over the next action a, is conditioned on the last observation oe only. "hh notation Ō(-) disregards logarithmic terms.
2

---

learning problem. For an initial belief b E B, the average reward of the MDP is defined as: P := - (1/T) -T-1 r(or)]bo =]]. When the underlying
belief
MDP is weakly-commuuicating it has been shown [5] that the optimal average reward p² :=
SuP+:B-A(A) P is independent of the initial belief b and the following Bellman equation admits
unique solution:
( P(db'lb a)o(db").
p² + v(b) g(6) + max
(2)
a
where g( = EEES Eoco ((s))())))(() denotes the expected reward under belief b, while P(- a) is a probability measure over the next belief Finally, u B - R represents the bias function and quantifies the cumulative deviation of rewards w.r.t. p* when starting from ò [2I].
3 Related Works
POMDP Learning. Learning in POMDPs is known to be challenging both from statistical and a computational perspective. When the observation model does not provide enough information to identify the latent states, we refer to the POMDP as hard. These intractable instances can be ruled out by introducing a full-rank assumption on the observation model. A quantitative version lower bound a 0 to the
of this assumption minimum singular value of the observation model, namely a. 3 a. The instances satisfying this assumption can be efficiently learned and define the class of a-weakly revealing instances.
first introduced in (16) and is formalized
POMDPs. The weakly-revealing assumption has been used both in the episodic [16 19] and the infinite-horizon average- setting. By focusing the latter, some works employed the simplifying assumption of having partial knowledge of the environment, in particular of the observation model. Among them, [3] provide a Bayesian regret of order ((T2/3) when compared against the optimal policy, while recent work from (26) proposes the Action-wise OAS-UCRL algorithm, which employs an estimation procedure with finite-sample guarantees that
leverages the knowledge of the observation model to learn the transition model. They reach a ((VT) regret guarantee when compared against the optimal policy. Several works have instead addressed the problem of fully learning the model parameters (1 3 (4). The standard approach relies on SD methods [ for learning the latent variable model. In particular, (3) are the first to adapt SD methods to samples collected under the adaptive class of memoryless policies. They consider stochastic policies where each action is chosen with a positive probability > 0 at each step and propose the SM-UCRL algorithm, which achieves a ((VT/(² regret guarantee when compared against this (less powerful) policy class. A different approach is taken in [32] where the regret is computed against the stronger class of deterministic (t = 0) belief- based policies. They present the SEEU algorithm, which alternates between purely exploratory and purely exploitative phases. During exploration, samples are collected using a round-robin policy over the available actions, after which SD is applied to recover model parameters. Their algorithm achieves Ö(T2/3) regret when compared against the optimal class of belief-based policies.
The introduction of our estimation strategy addresses two limitations of the aforementioned works. First, unlike the SEEU algorithm (32), we do not need to separate exploration and exploitation phases, as we can leverage samples collected during the exploitation phase to refine model estimates. Second, unlike the SM-UCRL B. we able to reuse samples from different policies, hence eliminating the need for stochastic policies (t > 0) that foster continuous coverage of the action space. We refer to Table I for comparison of our work with those mentioned above and Appendix H for a more extensive discussion on the matter.
4 Problem Formulation
We consider the infinite-horizon average-reward POMDP setting described in Section 2 Specifically, we consider the undercomplete setting [16], where the number of states less than or equal to the number of observations (S & O). Our focus is on learning the POMDP parameters represented by the observation model O and the transition model T (Ta)aEA We consider the class of
We provide precise definition of this quantity in the Notation section of Appendix C
3

---

Table 1: Table comparing the SM-UCRL, SEEU and the Mixed Spectral UCRL algorithm.
Property
SM-UCRL
SEEU
Mixed Spectral UCRL
No assumption on minimum entry of obs. model
X
No assumption minimum entry of trans. model
X
No assumption minimum action probability
X X X X
Works with memoryless policies
Works with belicf-based policies
Sample reuse with different policies Compares against the optimal belief-baset policy
V
Regret w.r.t. optimal belief-based policy
((T)
Ō(T2/3)
Ö(VT)
belief-based policies क B A, and we use P denote such set of policies. Before stating the main assumptions, we introduce some relevant quantities.
Let di d,-h0 (s, a) = Pr(s: = 8, a, = a/T. bo) be the 1-step state-action distribution induced by policy E P. with by B being the initial belief. Under mild regularity conditions (e.g., when the underlying
a unique limiting distribution dx (s, a) lim 2 .r.bu (s, a) (S x A) exists (see Proposition 5.1 in (25)) and it is independent of the initial belief by. From the quantity just defined, we derive the stationary action distribution d² e A(A) defined as d% (a) ==
MDP reakly-communicating
E.es dz (s, a). Let us now introduce the conditional state distribution w(. E A(S) defined as di (s|a) = dz (s, a)/ d (a), which is well-defined when di (a) O.
wg. (0,
The following assumptions represent the natural extension to the POMDP setting of the assumptions commonly employed for learning in (uncontrolled) settings (i.e., Hidden Markov Models ()) Assumption 4.1 (o-weakly Revealing Condition). There exists such that o > a.
This assumption quantifies the extent to which the received observations help identifying the underlying hidden states. It is equivalent to the more common fulntonnfulllraaa full-rank assumption largely adopted in problems involving the learning of Latent Variable Models [3] [2] (3]. was first introduced in
this form in [16] and then extensively employed in successive related works [99 20 26 It has been
shown that, without this assumption, learning becomes intractable (9]
Assumption 4.2 (Invertibility). For every action A, the transition matrix T, is invertible.
This second assumption implies that for any state-action pair (s, a) S A, its next-state distribution (-(+ cannot be recovered as a linear combination of the next-state distribution of the other state- action pairs. This condition is crucial for achieving identifiability and is widely used in the SD and POMDP literature
[ 32 34 IT].
Assumption 4.3 (Per-Action Ergodicity). For any policy π e P, unique limiting state-action
distribution d% (s, a) exists. Moreover, for every action if dz (a) > 0, then wi (0.x) > 0 Vs E S.
Assumption 4.3 extends the standard non -egeeeenyyyy assumption I employed under SD techniques. The motivation behind this assumption lies in the fact that SD approaches are applied for each action a separately. Hence, in order to fully recover the transition model T,, all states should be visited with positive probability when taking action (i.e., (a,77) >> 0). In Appendix H we show how related works B 32) tackling the POMDP setting rely on assumptions that subsume Assumption 4.3 A simple example when this assumption holds when the transition matrices (Ta)ae. have all positive entries, as we shall see in Section ( (Assumption 6.
discussion the reasons why some of these assumptions instead not required in the episodic setting is provided in Appendix H.2
Learning Objective. Our goal is to find the policy attaining Equation 2 in the policy class P. Our learning objective is to minimize the cumulative regret after T E N time steps, defined as:
Σ r(ox))
R = Tp*
(3)
where n² represents the average reward obtained by the policy satisfying Equation ( the reward obtained from the observation received by playing policy played time t.
while r(o:)

---

We remark that solving Equation 2 and computing such an optimal policy is known to be com- putationally intractable. Various methods have been devised provide an approximately optimal policy. Most of them focus on devising clever discretizations of the belief space and then solve the discretized instance 33 27 29]. In this work, however, we do not focus on this planning problem, but following common approach in the POMDP literature [32 34 13 we assume access to an optimization oracle capable of providing the optimal policy for a given POMDP model.
5
The POMDP Estimation Procedure
In this section, we present an adaptation of the common multi-view model employed for latent parameter estimation when using SD techniques [3 32).
5.1 The View Model
We now introduce a model-based strategy to estimate the parameters of the unknown POMDP which adapts the approach of [3] For each step e [1, T 2 in which a, E A, we construct three views containing the observations in three consecutive steps centered in i.e., 0t-1, 0t. 9--1 O. Let us use (bold) O, {0, 1) to denote the one-hot encoded vector corresponding to observation or and similarly for the two remaining views 0:-1 and 0++1. We further use vectors (a) E RO with E [1,2,3} to refer to the three different view vectors when conditioned on a, a, and such that 21.1 01-1, (a) O₂ and v3yi 01+1 respectively. Given a policy P, we define three view
matrices V.(am)) ROxS with E (1,2,3) associated with action É A. as follows:
Viam (o, 8)
lim Pr Pr (1(((e))) ola a, St 1-000
Pr (v(0=) o 02 0, s)
can be observed that the three views independent when conditioning on both 8 and ac. We also f..x)
denote with passs
(;,s)) the s-th column of matrix v/(,,)
Remark 5.1. By inspecting the three different view matrices separately, we can observe that for the second view matrix it holds that (a.,,,)) O, hence it does not depend either action policy
Differently, for the third view matrix, it can be shown that (5(*.²) OTT hence it is independent of policy æ. Finally, the first view matrix v/(0:)) depends on both the action and employed policy
Given this mieti-view model, the following result from [ applies:
Proposition 5.2. (Adapted from 3) Let V (1,2,3), a be a policy, and k(an)
2 b (a.5)] be the covariance matrix between views uy (0.5) and v (0.=), where & denotes the tensor product, and denote with the superscript the Moore-Penrose pseudo-inverse, We define modified version of the first and second views as:
Up
<0.,5) = =<((2)) 0i
(K( (((()=))
Vi
(a.x)
12
(a.T)
== K3,1
(a.+)
[K21
(a.m) (a.x)
V22
(4)
Then, the second and third moments of the modified views have a spectral decomposition as:
M(a=))
E
m
02
(a,m)
Σ
w (am))
p3,
(a.m)
X p3,8
(a.z)
M(
E
1
(a,))
02
(0,5)
(0,T))
Σ
w(aa))
p
(0,5)
& N3.s
(ast)
X P3,
(0,))
where the expectations are w.r.f the conditional state distribution (0.z) defined Section
When Assumptions 4.1 4.2 and 4.3 hold, the three view matrices v(a.s) e RxS with e (1, 3) associated with each action a A and policy и E are full-column rank and unique spectral decomposition exists D. As consequence, the original model parameters can be recovered. In particular, this can be performed by exploiting the following known relations between the columns of
*We exclude the first and the last T steps.
For the detailed expression of v((a.)) we refer Appendix A
5

---

the different view matrices:
33,
(a,a)
E
(0.5)
82 = a]
((a (axx) k(aa)
3,2
(K1,2
Mi.e"
(5)
33,
(a.T)
B[02
([ 82 = 02 a]
3,,
(K2,1
(1)))))) (a,t)
122
(6)
By applying SD techniques for each action a separately, we obtain estimates of the third view matrix V3 (a)))) hence of its columns M3,s
(a.=) Finally, when such estimates are available, the columns M1,s (a.a)
and 22,
(a.3r of the remaining view matrices can be estimated by inverting Equations (5) and (6).
5.2 The Mixed Spectral Estimation Procedure
We now show how combine samples coming from multiple policies, thus overcoming the limitations of existing approaches and leading to our novel Mixed Spectral Estimation. We
define set of different trajectories of samples 1 = {m)
L-1 such that the 1-th trajectory is generated
from policy Ti P and is defined as T = {(d), of)) Ni-1 Additionally, we introduce the related
set T,(% {t e [1 10-) 2] s.t. af a} which contains the time steps when action is selected in the 1-th trajectory. Let mi = [T,(a) denote its cardinality. For each & E T, (a) we construct the
three corresponding views (u(o.)) 222 (a.1) ((2.)) (o--1, Or, 0141). where the superscript refers to the trajectory collected using MT Our approach uses views from all the L trajectories to define new covariance matrices k(g,4) with v, E {1, 2, and v', These are weighted versions of the original covariance matrices and are defined follows:
K k(a.))
n
(a) E
(a.)
(a.)
(a) ni
pv (ad)) @
Pus
(a.))
(7)
(a)
N
#ES
where N(
ASS) denotes the conditional state distribution determined by policy πı and action a. We show that the following result holds when combining multiple policies. Its proof deferred Appendix
X1-1 "i while w(..)) w
(a)
Theorem 5.3. Let I == {T be a set of trajectories collected using the set of policies {m) We define a modified version of the first and second views as:
01 y(a.1)) = (a.L)
(K(
(a.1)
((a1))
K3. (K(aL))
(8)
where the covariance matrices are defined in Equation 77. Let (a.l) = (1/N E/T ni w()), then, the second and third moments of the modified views have spectral decomposition as:
1 (a)
1
(a)
E
(a.1)
02
[a.l)
Σ
w
(a.L)
(a) pass s
(a) &
pa.s
N/aa
(a)
1=0
L-1
(a)
(al))
(a))
(a.1)
Σ
(0) w (o.L)) p3. 0 p3 2 P3.0
ni
N
where the expectations are w.rt. the conditional state distributions (0.1).
(a.1) are modified using the weighted covariance This theorem shows that when the views v ((a.1) and 02
matrices K k(a,F) defined in Equation 77 instead of the covariance matrices k(aa)) "ee" associated with policy mi the new second and third order moments have spectral decomposition whose conditional
v.a""
state distribution (a. is average of the original conditional state distributions, each one weighted (a)
proportionally by the cardinality ni (a) Importantly, as discussed in Remark 5.1 the columns 33,e of the third view matrix do not depend on the employed policies but only on action hence in
Theorem 5.3 we do not report the dependence on the mixture of the policies. The independence of the third view matrix from the employed policies plays crucial role in proving Theorem [.3)
Algorithm Pseudocode. The estimation procedure of the quantities described above, and of the esti- mated POMDP parameters, is described in the Mixed Spectral Estimation approach presented in Algorithm [
For each action a, the view vectors are computed for all the policies, and they are used to compute the mixture covariance matrices (Line 8). Given the new covariance matrices, the

---

Algorithm Mixed Spectral Estimation.
Input: Trajectory set (m) where each have 72 ((o),
2: Output: Estimated Observation model Ô and Transition model (Ta)
3: for a AA do
4: for é [0,
do 5: Construct views v/..1)) 0:-1, 1221 Ot, V3.1" oc+1 for any te T.
(a.1)
6: end for
7: Compute N
Σt-1 (a)
8:
Compute covariance matrices for v, v/ (1,2,3): Li-o 210T
((0_)) MP
wart @ u
(e.))
9:
Compute modified views:
(n.4)
L)
(a.))
slaa))
R(att
R((l))) (a.) 02.1
3,2
2,
10: Compute second and third moments:
M (a.2
(a.d) olo)))
1E7)
Mg L)
(a.)
U.t @ (o.))
0 1,
M(")
tET((0)
11: (r(a) = TENSOODECOOPOSTIOON ,M
12: Compute (2(0 inverting Eq. (6)
13: end for
14: Define a* angmax N(a)
for a A do
16: Match the columns of each (a) with ((**))
17: Permute the columns of P25") using the same permutation adopted for Vi(")
18: end for
19: Compute @ according Fq.
for a A do
21: Compute T. according to Eq. 10
22: end for
modified views are computed for each E ((()) with E [0, 1] (Line 9). The modified views then used to compute second and third-order moments (Line 10), and tensor decomposition routine (line 11) is run for each action separately, thus obtaining the estimated view matrix Viaa) By able to derive estimate of the second view matrix (((0)_ As noted in Remark 5.1 the second view matrices are identical across all actions, thus satisfying Vi( O for any action a. Since spectral methods recover the columns of the original view matrices up a permutation of the hidden states s [ this equivalence allows us to align the columns of the different (7() by appropriately permuting them, thus ensuring that the represented states ordered consistently, as also done in 3. To do that, we define a* argmax N/(a) and choose ()(a)) as the reference view that the other views should match It is possible to show that when the estimation of each view is sufficiently accurate, the correct permutation permutation step is completed, the observation and transition model are computed as:
inverting Equation (6),
be found for each P7(a) When the
①
1
Nr(a (()))
NL
"We adopt the Robust Tensor Power (RTP) method from 11 as tensor decomposition strategy.
This way, for each action the columns of (2(0) permuted to minimize the 1-norm error w.r.t (a(*))
7

---

T. o )))))))
(10)
where N₂ EaEA NL Thus, the estimated observation matrix is obtained as weighted combi-
nation of the second view matrices V2(00) while each transition matrix recovered by inverting the relation presented in Remark 5. and using the observation matrix computed as in Equation (9). The
computational complexity of the presented approach is discussed in Appendix [ Algorithm Tejooys
the following guarantees, which are proved in Appendix
Theorem 5.4. Let ① and (TaloEA be the observation and transition model estimated using Algo- rithm respectively. Let Assumptions 4.1 and4.2) hold and let Assumption 4.3 be true for any Ti with IE [0, L ---1,, ll. Let å (0, (0) then for a sufficiently large number of samples N..) holding for every action E A, with probability at least - 35, it holds that:
0
7 F
Co ÇiD)
log (O/8)
Ta - Tol
CTS as(O)((o))
log LO/5)
NL
N/..
where ((D)
03,1
(LL
V
min (12.33, (s
w(L) min
min
(L) a min and 031
w (a,t)
min a (osKKK klal))), while Co and Cr are suitable constants. anA
We highlight that Theorem 5.4 requires minimum number of samples N( for each action (this number should satisfy Equation (38) reported in Appendix (B). which depends on the set of L trajectories. Nevertheless, it places restrictions the length of the individual trajectories ni allowing for certain trajectories not to contain a specific action a. This aspect will be significant for proving the regret guarantees of our Mixed Spectral UCRL approach.
6 Mixed Spectral UCRL
Algorithm 2 Mixed Spectral UCRL.
1: Input: Confidence level 8, length of initial episode
The Mixed Spectral Estimation proce-
To. total horizon T
dure can be easily combined with an optimistic
2: Initialize: | <- 0, I 0, belief bn uniform over
strategy resembling the UCRL approach for
states, Trajectory set r
MDPs 14]. We call this new algorithm Mixed Spectral UCRL, and we describe its workflow in Algorithm 2 During the first episode, a uniform policy To (Line 3) to collect a suffi- cient amount of samples for each action A in order to provide a first estimate of the POMDP parameters. The whole interaction horizon is divided into episodes of different lengths. At the beginning of each new episode I, all sam- ples collected up to that moment are used to estimate the new POMDP parameters according to Algorithm (Line 7). Based on the estimated
3: Build trajectory To from uniform policy mo for To steps
use
4: r - T U {TO)
5:
( To. 1 1, Set N: -n Va e A
6: while 1 T do
7: Run Algorithm Tuing trajectory set I and ob-
tain estimates Ô and T (Ta)aeA
8: Build a confidence set C((d:) of admissible
POMDPs
9:
Compute policy कı and optimistic Q: (Eq.
10:
7. - (). nz(") < 0 for all a e A
(
11:
Observe o,, get reward <- r(o.)
POMDP 2. we build high-probabiligg confi-
12:
Update belief b, using Equation !
13:
Set a. (b.)
dence set (7)) of admissible POMDPs accord-
14:
while f T mi
N((0)) do
ing to the bounds defined in Theorem 5.4 us-
ing a varying confidence level & = 5/ (35
15:
Execute as, Set ni
(ax)
m, (ex) +1
Observe 0c+ get reward (or+1)
(Line 8). The optimistic policy and the associ-
17:
Update belief to be+1 using Equation ! and estimated ① and To,
ated POMDP are then computed at the begin- ning of episode according the program:
18:
Set a++1 < m. (b++1)
(Ti, 21) E argmax P(T, ②)
(11)
19:
< as)
TEP, (EC()))))))
20:
fett-t+1
21:
end while
where p(T,, ② is the average reward of policy in the POMDP instance O. As specified in Section[4 we assume access to an oracle to solve Equation II] Then, each episode terminates
22:
I' -- I' u {m]
23: Set Nala) - N((a)) + ni
Vae
24: Set 1
25: end while
8

---

when there exists action A such that the number of times m/)) it has been chosen during the I-th episode exceeds the total number of times N(()) it has been chosen since the beginning (Line 14).
6.1 Regret Analysis
Before proceeding with the analysis of the regret of the Mixed Spectral UCRL algorithm, we remark that when the estimates of the POMDP parameters are accurate enough, the belief vector by computed each step using the estimated parameters close the real belief b, To the best of our knowledge, the results in the literature [32 34 26 10 15 that relate the belief error || - by I with the estimation error of the model parameters all hold under the following one-step reachability assumption.
Assumption 6.1. (Minimum Value Transition Model) The smallest value in the transition matrices satisfies c== min (s(s'(s) 0.
a,''ES aEA
Note that Assumption 6 implies the Per-Action Ergodicity (Assumption The regret for Mixed Spectral UCRL can be expressed as follows. Its proof is deferred to Appendix C
Theorem 6.2. Under Assumptions 4.1 4.2 and 6.1 let 8 (0, 1/2). If the Mixed Spectral UCRL algorithm is run for sufficiently large number of steps T. with probability at least 1 26, it suffers regret bounded as:
D(SA)
SAOT 8
Rr < O
TO log?
os(O)
where ((1) min (0) and (() is defined as Theorem 5.4 D bounds the spar 1e(0,L-1)
8 of the bias
function appearing in Equation and is defined in Proposition G.7
This algorithm overcomes the limitations of SM-UCRL since does not require a constantly exploring policy, and removes the need for a phased algorithm done for SEEU. By efficiently reusing samples from different policies, we enhance the online learning of POMDPs by improving the current regret guarantee of (1/2/)) established by the SEEU algorithm.
7 Numerical Simulations
In this section, we analyze the estimation error of the Mixed Spectral Estimation approach under different belief policies and we show the performance in terms of regret of the Mixed Spectral UCRL algorithm when compared against state-of-the-art approaches. Further experiments and simulation details are provided in Appendix J
Mixed Spectral Estimation Algorithm. This first set of experiments studies the estimation errоr achieved by the Mixed Spectral Estimation algorithm. In particular, we evaluate our method on POMDP instance with sizes described in Figure ! The estimation error is measured using the Frobenius norm of the observation matrix and the transition matrices (one per action). Figure reports the average results over 10 runs. The simulation splits the interaction horizon into 10 episodes of equal length, and for each episode, we use different belief-based policy for data collection. As observed in the figure, the total eгror decreases the number of collected samples increases, demonstrating that our approach is able to efficiently combine data from different policies.
Regret Comparison with state-of-the-art Algorithms. In this second set of experiments, we compare our Mixed Spectral UCRL algorithm with SEEU and SM-UCRL [3] The regret is measured w.r.t. the oracle whose policy satisfies Equation (2) and has full knowledge of the model parameters. As observed in Figure 2 the SM-UCRL algorithm experiences the highest regret since (i) it does not reuse samples across episodes, (ii) it relies on the weaker class of stochastic (1. > 0) memoryless policies. This forced exploration leads constantly selecting suboptimal actions, hence
&The span of the hias function is defined as: span(v) == max n(b) minges u(b).
9The codebase can be found at htttttsss//gtthbb com http://awoo..oeaeeeoeoo/osssaaaa
.it

---

Estim. Eiror -11m
Regret (10*)
2
0.5
Num Epizodes
Horizon (10")
To T1
SMUCRL
SEEU
Mixed Spectral UCRL
Figure 1: Estimation error of the Mixed a POMDP with Figure Regret comparison on POMDP with S 4, A = 3 and O = 4. (10 runs, 95 %c.i.).
Spectral Estimation
= 3 = 4 (10 runs, 95 %c.i.).
resulting in higher regret. We also observe that the Mixed Spectral UCRL algorithm outperforms the SEEU algorithm. This result is in line with the theoretical guarantees, as the regret of SEEU scales with ((7233). Besides the alternating exploration-exploiitie SEEU also be attributed to its reduced sample efficiency since its estimates only rely data collected during the exploration phase, hence discarding those collected during the exploitation phase. Finally, in Appendix [] present a regret experiment where Assumption 6.11is violated in order to show the robustness of our approach with respect to the failure of this assumption.
phases, the inferior performance of
8 Conclusions and Future Directions
In this work, we tackled the problem of learning using spectral methods the infinite-horizon average-reward POMDP setting. We showed that spectral techniques can be extended to belief-based policies and, through our Mixed Spectral Estimation approach, we answered positively to the open question of whether it possible to combine samples coming from different adaptive policies. We provided finite-sample guarantees for the devised estimation algorithm, and we showed that the error of the different parameters conveniently scales with respect the number of employed samples. We combined the new estimation algorithm with an optimistic approach, Mixed Spectral UCRL, and provided the first algorithm achieving Ö(VT) regret order when compared against the optimal belief-based policy, by leveraging the new sample reuse strategy, and suitable episode stopping condition. Finally, that our approach has improved performance over tfateoof-the-a algorithms. As future step, we will study whether it is possible to relax some of the assumptions employed in this work, such the one-step reachability (i.c., Assumption 6.1.
validated both approaches through numerical simulations, and we showed
Acknowledgements
This paper supported by FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR-PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence).
References
[1] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. J. Mach. Learn. Res., 15(1):2773 2832,, jan 2014.
[2] Animashree Anandkumar, Daniel Hsu, and Sham M. Kakade. A method of moments for mixture models and hidden markov models. Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors. Proceedings of the 25th Annual Conference Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 33.1-33.34, Edinburgh, Scotland, 25-27 Jun 2012. PMLR.
[3] Kamyar Arizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of pomdps using spectral methods. In Vitaly Feldman, Alexander Rakhlin, and Ohad
10

---

Shamir, editors, 29th Annual Conference on Learning Theory. volume 49 of Proceedings of Machine Learning Research, pages 193-256, Columbia University, New York, New York, USA. 23-26 Jun 2016. PMLR.
[4] Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 1967.
[5] Dimitri P. Bertsekas. Dynamic Programming and Optimal Control, 3rd Edition. Athena Scientific, Belmont, MA, 2005.
[6] Ramaprasad Bhar and Shigeyuki Hamori. Hidden Markov Models: Applications to Financial Economics, volume 40 of Advanced Studies in Theoretical and Applied Econometrics. Springer Science+Business Media, New York, NY, 2004.
[7] Joseph L. Bower and Clark G. Gilbert, editors. From Resource Allocation to Strategy. Oxford University Press, Oxford, UK, 2005.
[8] Noe Casas. Deep deterministic policy gradient for urban traffic light control. CoRR, 0os/1703.09033 2017.
[9] Fan Chen, Huan Wang, Caiming Xiong, Song Mei, and Yu Bai. Lower bounds for learning in revealing POMDPs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 5104-5161, PMLR, 23-29 Jul 2023.
[10] Yohann De Castro, Elisabeth Gassiat, and Sylvain Le Corff. Consistent estimation of the filtering and marginal smoothing distributions nonparametric hidden markov models. IEEE Transactions on Information Theory, 63(8):4758 4777, 2017.
[11] Zhaohan Daniel Guo, Shayan Doroudi, and Emma Brunskill. A pac rl algorithm for episodic pomdps. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th Interna- tional Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 510-518, Cadiz, Spain, 09-11 May 2016. PMLR.
[12] Daniel Hsu, Sham M. Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 78(5): 1460-1400, 2012. JCSS Special Issue: Cloud Computing 2011.
[13] Mchdi Jafarnia Jahromi, Rahul Jain, and Ashutosh Nayyar. Online learning for unknown partially observable mdps. In Gustau Camps- Francisco J. R. Ruiz, and Isabel Valera, edi- tors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 712-1732. PMLR, 28-30 Mar 2022.
[14] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563-1600 2010.
[15] Bowen Jiang, Bo Jiang, Jian Li, Tao Lin, Xinbing Wang. and Chenghu Zhou. Online restless bandits with unobserved states. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 15041-15066. PMLR, 23-29 Jul 2023.
[16] Chi Jin, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient rein- forcement learning undercomplete pomdps. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[17] Vikram Krishnamurthy. Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing. Cambridge University Press, 2016.

---

[18] Jesse Levinson, Jake Askeland, Jan Becker, Jennifer Dolson, David Held, Soeren Kammel, J. Zico Kolter, Dirk Langer, Oliver Pink, Vaughan Pratt, Michael Sokolsky, Ganymed Stanek, David Stavens, Alex Teichman, Moritz Werling, and Sebastian Thrun. Towards fully au- tonomous driving: Systems and algorithms. 2011 IEEE Intelligent Vehicles Symposium (IV), 2011.
[19] Qinghua Liu, Alan Chung. Csaba Szepesvari. and Chi Jin. When is partially observable reinforcement learning not scary? In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 5175-5220. PMLR, 02-05 Jul 2022.
[20] Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvári, and Chi Jin. Optimistic MLE A generic model-based algorithm for partially observable sequential decision making. CoRR, abs/2209. 14997, 2022.
[21] Sridhar Mahadevan. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Mach. Learn., 22(1-3):159-195, 1996.
[22] Lingsheng Meng and Bing Zheng. The optimal perturbation bounds of the moore-penross inverse under the frobenius norm. Linear Algebra and its Applications, 432(():956-966) 963, 2010.
[23] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In Proceedings of The 33rd International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 1928-1937. PMLR, 2016.
[24] Elchanan Mossel and Sébastien Roch. Learning nonsingular phylogenies and hidden markov models. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 366-375. ACM, 2005.
[25] Alessio Russo, Alberto Maria Metelli, and Marcello Restelli. Efficient learning of pomdps with known observation model in wewage setting. CoRR, abs/2410.01131, 2024.
[26] Alessio Russo, Alberto Maria Metelli, and Marcello Restelli. Achieving Õ(VT) regret in average-reward pomdps with known observation models. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pages 1168-4176. PMLR, 03-05 May 2025.
[27] Naci Saldi, Serdar Yüksel. and Tamás Linder. On the Asymptotic Optimality of Finite Ap- proximations to Markov Decision Processes with Borel Spaces. Mathematics of Operations Research, 42(4):945-97) November 2017.
[28] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, 0oss/1707.06. 707.06647, 2017.
[29] Hiteshi Sharma, Mehdi Jafamnia-Jahromi and Rahul Jain. Approximate relative value learning for average-reward continuous state mdps. In Ryan P. Adams and Vibhav Gogate, editors, Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 956-964. PMLR, 22-25 Jul 2020.
[30] Le Song, Animashree Anandkumar, Bo Dai, and Bo Xie. Nonparametric estimation of multi- view latent variable models. In Eric P. Xing and Tony Jehara, editors, Proceedings of the s1 International Conference on Machine Learning, volume 32 of Proceedingy of Machine Learning Research, pages 640-648, Bejing, China, 22-24 Jun 2014. PMLR.
[31] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
[32] Yi Xiong, Ningyuan Chen, Xuefeng Gao, and Xiang Zhou. Sublinear regret for learning pomdps. CoRR, abs/2107.03633, 2021.
12

---

[33] Huizhen Yu and Dimitri P. Bertsekas. Discretized approximations for POMDP with average cost. CoRR, 0os//107..1144 2012.
[34] Xiang Zhou, Xiong, Ningyuan Chen, and Xuefeng GAO. Regime switching bandits. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 4542 4554. Curran Associates, Inc., 2021.
[35] K.J Åström. Optimal control of markov processes with incomplete state information. Journal of Matheaatical Analysis and Applications, 10(1):174-055, 1965.
13

---

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

---

Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification: All the theoretical claims reported in this work are supported by complete proofs. The proofs of Theorems 5.3 5.4 and 6.2 are reported in Appendix [ B and C respectively. The auxiliary claims used in the proofs are also reported in the Appendix, together with their associated proof' or references. The employed assumptions are clearly stated and justified.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes].
Justification: The paper provides the description and pseudocode of both the Mi xed Spectral Estimation and Mixed Spectral UCRL algorithms, together with the hy- perparameters used for the experiments which are clearly reported Appendix []] The description of the POMDP instances and the way they are generated are fully described in Section 7 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
15

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes].
Justification: The released code provides scripts for running both the experiments on the estimation of the POMDP parameters and also the experiments on the regret, which compare against the different baselines.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.cc/putt wttp:ccccppppppiiia...ca.ococppa cetpi///giidee//deeuubbbiiii
hat////ooeubiieeea seabbbisssionn assionnoicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes].
Justification: Information about the experimental settings are reported in Section 7 More details the way instances generated, the employed hyperparameters, and the reasons behind their choice are provided in Appendix[] Further details are contained the submitted code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
16

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes].
Justification: Both the experiments the estimation are repeated multiple times, and the confidence level of the presented results is reported in the plotted figures. Their calculation is reported in the released code.
and the experiments on the regret
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes].
Justification:
The information on the employed hardware is reported in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:p::s//errppp..cpcbbl//////s
Answer:
[Yes].
Justification:
We checked the guidelines and we are compliant with them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
17

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This work is mainly theoretical, and its goal is to advance the field of Machine Learning. We do not see any negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymenn of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-us should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA].
18

---

Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssiippssiiii thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes].
Justification: Yes, the released code is well documented. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsoureing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
19

---

Answer: [NA]
Justification:
The paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA].
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not non non- stanstandard components.
involve LLMs as any important, original,
Please refer to our LLM policy for what should or should not be described.
20

---

Appendix Organization
We provide here an outline of the Appendix.
Section and present the proofs of the three theorems reported in the main paper.
Section D provides some auxiliary results employed for the proof of Theorem 5.4 They are mostly related to the guarantees derived from the application of Tensor Decomposition methods.
Section gives an overview of the Symmetrization and Whitening steps, which are implemented on the third-order tensor before applying Tensor Decomposition techniques. It also introduces useful quantities that are used throughout the appendix.
Section F provides a new bound relating the sum of successive belief errors with the error in the estimated model parameters.
Section presents a miscellanea of useful results.
Section H
compares our work from a theoretical perspective with the related works of 3 and 32
and compares spectral approaches with Maximum- -iiuumm--iieiooodd estimation techniques.
Section discusses the computational complexity of the Mixed Spectral Estimation method.
Finally, Dection[[provddee experimental performances POMDP instances different charac- teristics, together with details about the numerical simulations presented in the main paper.
A Proof of Theorem 5.3
In this section, we provide the proof of Theorem 5.3 For clarity, we report its statement here.
Theorem 5.3. Let I = (m)(=o) be a set of trajectories collected using the set of policies (mil We define a modified version of the first and second views as:
L).L) 1 (1 = 3,2
(K(
0i (a.1)
s(a)) = ((ab)) (K!GID)
(8)
where the covariunce matrices are defined in Equation 7 Let w(,l)) = (1/N(a) EL "i w(al), then, the second and third moments of the modified views have spectral decomposition as:
(0)
M
M
1
E
01
(a.))
2
= Σ ((a.))
(a) (a) 13, & M3.0
N(a)
M L)
(a)
(a.))
(o.1) = Σ
w (a.L) (a)
nt
& v/
u3. @ 23. & Ps..
where the expectations are w.r.l. the conditional state distributions (a.1)
Proof. Before proceeding, is relevant to highlight the relation between the view matrices. We use v(lal), v(ao.) and v-(a.)) to define the views associated with policy and action We further recall that under the a-weakly revealing assumption (4.T) and the invertibility assumption of the transition
matrices (4.2). the view matrices are always full-column rank 3 We define the following quantity:
T Tam
Σ Pzy (a'la) T. d'
(12)
with Pm, (-la) ((AA being probability distribution induced by policy and conditioned action a. As observed in (25), this distribution always exists under the employed assumptions. In particular,
Pm, (a'la) denotes the probability of having chosen action a' in previous time step (say t 1) conditioned on the fact that action a is taken in the successive time step (say l). Intuitively, Ta represents the mixture transition matrix defining the state transition from previous step (f 1) to successive one when action a' is chosen t-1 1 by policy म; and the next action chosen by the policy in step is a. Let us also recall that (a.1) represents the state distribution induced by policy T and conditioned action such that w (e.1) is the probability of being in state when choosing
21

---

action Using the definition in 122 we can also define the state distribution at the previous time step 1) as:
g(a.1) = =TT
(a.))
(13)
with g(a.)) E A(S) and such that g!a.0) represents the probability that state s visited in the previous time step (t - 1) conditioned on having chosen action in t.
Having defined the previous state distribution g(a.f) in Eq. (13) and inspired by the multi- -vew model on Markov Chains of [I] we can now express the views using the following relations:
vy(a.)- = O diag (<(a.)) Ta,m. diag (w)l
(14)
vz(00) O,
(15)
v/(a)) O T.
(16)
From the relations stated above, we observe that the second view v/(a+) corresponds to the observation model, thus it depends neither on the action nor on the employed policy. Hence, we may refer to it
simply as V2. The third view depends on the action but not on the employed policy, so we may refer to it also using va(a), Finally, the first view depends on both the action a and on quantities related to the employed policy Tτ.
Let us now recall the definition of the covariance matrix associated with a single policy ni, as reported
in Proposition 5.2 In particular, we will use the notation K k(aa)) to highlight that the covariance matrix depends on policy P. thus distinguishing it from the mixture covariance (in bold) K (a) resulting from the combination of L different policies.
(a.1) Analysis of Covariance Matrix k(24), We start by considering the covariance matrix K32 oxx obtained from a single policy mi:
K k(a.)) (a.))
(a.))
(a.1) 02
vi(ua)) diag (wsaat) (vila))) v((()) diag (wlalt) Vz2
E
where (al)) E A(S) is the state distribution conditioned on action a and diag (wla.)) E RSS represents diagonal matrix whose diagonal values correspond to w(a.t), Let us now recall the definition of the mixed covariance matrix in Equation The following holds:
(a)
(a.1) (a.1)
033 2
02
(17)
N
(a)
(a..)
1
(a)
k(a.))
N(a)
T4
(18)
(a)
vila) diag (waa))) VØ
Nvla)
n4
(19)
vi(a) diag
Ny(a)
Σ
n
(a)
w((d) V.
(20)
I-n
= vi(a) diag
(w(e.L)
VØ
(21)
O T diag (w())))
T,
(Follows from lines 15 and 16
where in line 19 we used v/ Vi (a) for any I, and v/ 1/2 for any and I, hence highlighting
the independence of both view matrices from the used policy m. In line 20 we introduced the new
state distribution ((.L) e A(S) such that w(..t) = (1/N(o) E (a) wal))
22

---

II Analysis of Covariance Matrix K211 Let now consider similar relation for the covariance
matrix K (a.LL) ROxO combining L different policies. We have that:
3,1
n
(a)
E (a.()
1/ @ 00f{
(a.))
(22)
N
(O)
n/
(a)
K311
(23)
Σ
1
(a) ((ai)) diag (wlal)) (via.)) T
V/3
(24)
(a) 0 OT diag (wlal)) diag (w)aa)))
To diag (Ela.)) T
ni
(From lines
14 and 16)
L-1 Σ
ni
(0)
a. OTT
T
diag (slan)) TT
(25)
(()
1-0
= -OT.
To.m diag (E(o.)
Ta
(Associative property)
.v(aj
O T diag (wrlal)i)
diag (wsla.t)) -1
Σ 1-0
T diag (slue) O0
N
(a)
ny
(26)
viSa) diag (u)l (vylart)) T
(From lines and
16
Dt-1 ((a)) TI diag (cla))) ) diag (w) -1 defines
where in the last line the mixed first view matrix.
(((a 0
M! Analysis of Covariance Matrix K( By applying similar steps to those employed for covariance matrix k(a.") we are able to show that:
(e.L) K 2,1 = 1/2 diag (wlart) (MaL)))
(27)
We are now ready to provide the proofs for the second and third moments. For simplicity, we will just provide the proof for the second moment matrix M (a,2) since the proof for the third moment tensor ( follows analogous steps.
23

---

Proof for the second Moment matrix M2 (..44) defined as follows.
The relation for the mixed second moment matrix is
M (a
E
0 X
(28)
(nlaai) ((KI))2)))
(a) E
K
())
v/a1) (a.))
K
x(aL))
(29)
No.
i-n
-K322 L)
K (())))
t
Σ
n
(a)
E
(ad) fall) ") ((
U2
(K2)1 )
k(
1-0
(30)
-K(al)
(x(
k(O!!)
((x54
k(aa))
(31)
T
-K(at)
k((a
(32)
L) (K(0 k(
(33)
(v3 diag (wll)))) vōT] (vz)) ' diag (wlal))) -1 (v
vilual) diag (wolat))) (vz TI
(34)
Vi(al diag (wolunt)) (v!l)) T
(35)
Σ (L.L) u E 13,5
(36)
SES
where line 29 holds since 0 (a.1) & o (a.1))
T
while line 34 holds for the relations of
covariance matrices found in the above points.
The simplification steps made from line 34 to line 35 are done considering that the multiplication of a matrix and its pscudoinverse while projecting along the smaller space of size S produces Iss, an identity matrix of rank S. In particular, by applying the definition of the Monroeee inverse of matrix, we have that V (V₂2 V2) VV2 Since the pseudo-inverse of transpose corresponds to the transpose of the inverse, we get that (V2T)* = V2(V V/2-1. Hence, the expression in line 34 can be simplified as:
V (V21)* (22T12) (V2 1/2) Is-
Similar steps also lead to (v(aa) t (((a)) 1s.
Finally, the last equivalence in line 36 concludes the proof.
B Proof of Theorem 5..4
Theorem 5.4. Let & and (TaJasA be the observation and transition model estimated using Algo- rithm 7 respectively. Let 4. annd).2d.. hold and let Assumption 4.3be true for any ni with Ie [0, L 1I. Let d E (0, 1/(3SA)), then for a sufficiently large number of samples (aa) (a) for every action E A, with probability least 3S it holds that:
L. holding
10 10-6 F
Co 5(L)
SAL log log(LO/8)
To Tol
CTS os(())(L))
AL log( LO/8)
<
<
N₂.
N (a)
L
24

---

where ((b) =
x(L)
(1.3,, as (V((a))))
w(L) min
min (a.L) =
and x(L)
3,1
aEA min
3,1
min as( (K k(a,)), while Cg and Cp are suitable constants. aEA
3,1
Proof. We recall that Spectral Decomposition techniques separately applied for each action A
and each of them outputs estimates of the third view Vg From the columns μ3., of the third view, estimates of the columns a2, of the second view matrix be computed by inverting Equation (6).
We remark that the second view is equal for all actions a and it corresponds to the observation matrix
O. Since require that the number of samples .V(.) satisfies conditions in Equation (95) and (TO2).
Lemma D.I can be used to bound the error of the columns P2,a of the second view matrix, thus having:
16E (a.
12.
(a.L)
112 &
(37)
os ( 3,1
(1)
holding with probability least 36, and with (a.
EM
defined in Lemma D.1
Condition for Column Permutation The next step algorithm
consists in permuting the view !
matrices (a. for each action in order to minimize the I-norm error with respect to view matrix p-(a* L) where a* e arg max No 11 The permutation found for each estimated matrix (o is
as
then applied as well to the associated third view (.
(o.L) is estimated sufficiently well. Guarantees the permutation achieved when each column 242.8
Let us denote with do
min 5
10(1s) 0(-1s'|l the minimum distance between columns of
O. As observed in [3]. when the estimation error is lower than do/4, 4, the columns can be permuted without error. Hence, we derive here the minimum sample condition such that the estimation error of each column (reported in D.I is bounded by do/4:
2
128 /2 /2 7
(0a 0)2L
N(()
8L log
3
do os k(
( Moi
(a.L)
min, as (V/a
By combining the condition above with those required for the bound of Lemma D.1 obtain:
8L.²
log 20 + 0)
N((1 I(aL)
(38)
(1- 7)
8
where
2
[o.L) max
3
do 0.5( (o.KK (a
(aluu min, a
as (Viaalii)
2vΩ
4
(a.L) Wiin
min, (s(V(aL))) 12
[os(K((a))) 3,1
}]
Differently from the notation used the pseudocode of the Algorithm, here add the superseript the second view, thus specifying that the estimate depends on L policies.
Thhhs choice is motivated by the fact that, without knowledge of the parameters characterizing the different (a.L) assume that the view presenting the lowest error is the one associated with the action that has been Ca
chosen the highest number of times.
25

---

Bound on the Observation Model Error After the permutation operation, we can finally combine the obtained view matrices 2g L) as shown in Equation
(
to obtain unique matrix (4) such that:
(L))
1
Σ
No.
(a) ((aL)
Nr. aEA
with Ny. Eee N Let us denote with ( the s-th column of view matrix (2()), From the bound defined in Equation (37) and using a union bound argument, we finally get with probability at least 1 3.4 that:
16v A
(L) 22,6
(39)
(L)
3,1
where:
3
10g(40
2v/2 I-n
8L (102++0)))))
[1()) min
ming, (s(
(LL) EM
&
NL.
(40)
V Valhh m (V((ua)))))
@ (1(
and 03 (.(L) = min w (a.1) and (LL) asAA
= min 0 ( (a. 3,1
min
3,1
aEA
We notice that a further VA term appears (39 as a result of the union bound, and we stress that
the minimization over the singular values is done considering both E 21,2,3) and a.
Since the result in (39) is independent of the single column s, we can easily extend to the whole observation matrix and finally get:
16v SA (L) (L)
0
i
12,3
(D)
(L) 12,
M
(41)
SES
holding with probability at least 1 35A5. By simplifying the notation and highlighting the most relevant terms in the bound, we get:
Co (LL)
SAL log (og/))
(42)
N
with Cc being suitable constant and ((L) being defined as:
((L)
(L) 3,1
V
min (V M,a
(43)
Bound on the Transition Model Error By following Algorithm [ the s-th row of each estimated transition matrix T. is computed as (s -) 61 p.. Let us analyze its associated error. We have:
-a(s,-)-Ta((5) - -Ta(s)) >/2 = 10 La. - tt ttplo L)
33,
0 θ 2
Lo.L)
(o,L)
[t
13,
13,
13, 1
(b)
(a.1)
Let us now analyze the different terms separately. Concerning the term (a), we use i) and ii) we first apply Proposition D.6
13.3
< 1
on the spectral norm of the pseudo-inverse of matrix and then we use Proposition D.7 to bound Ot ôt and obtain:
2(1
00
0
4 10- Gll
40
Ô 4 4-16/5A2L0 (L)
(a)
2
(0
os( 0
Os(O)
(s 2(4)
26

---

Analogously, for the second term (b), we apply i) Proposition D.6 to bound ||O1|2 and ii) we use Lemma D.2 to bound the error of the estimated view vector, thus obtaining:
28E (a.L)
14 (0.
M
(O
(s(O)
Since Proposition D.6 holds under the condition number samples N₂ based on the bound in 42
100 Of12 & (1/2)as(O). require minimum
It should satisfy:
2Co
LO
NL
(s()
SAL log
8
(44)
The conditions defined in 38 together with the one just stated above on the total number of samples Nz determine the sufficient conditions for the theorem to hold.
Going back to the bound on the estimated transition matrix, by combining the results reported so far, we get with probability at least 1 3S Ad:
[T( (s 0/1
64 SANSACK (L)
M
28
(a.L) M
CTVSA
La M as(O))
S (
(T)
())
3,1
(a.L) where Of is suitable constant term, while used here quantity EM z(a.L) CM M
for which holds
both Ed & EM
LL) ((a,L) and (a.L)
since it is defined as:
log(d0L/0) N
3
2V2 T-n
&L 1og((0==0)22/)))
(V
min, (s(
N(
L(,L) MM
V min as (V(aaa)))) 73 +
(45)
(D)
V (L)
xLL) scaling with rate 1/N(") L differently from the rate 1/Nr of MM defined in Equation (40). Since this
bound holds for any row of the transition matrix, we can derive the error on the whole transition matrix as:
C V
To Ta 1
Ta(s,-) To #ES
Σ
(46)
03 (0)03 (L)
holding with probability least 1 3SA8 and presenting additional VS term. By simplifying notation and highlighting the most relevant terms in the bound, we get:
O
AL log(LOO/0
Ta
(s(O)((E))
V
N!aa)
where Cr is suitable constant and ((L) is defined in Eq. (43 This last step concludes the proof.
C Proof of Theorem 6.2
This section will present the proof for Theorem 6.2
showing the regret guarantees of the Mixed Spectral UCRL algorithm. This result makes use of Theorem to the estimation guarantees of the Mixed Spectral Estimation approach presented in Algorithm [ and it makes use of the new bound on the belief error provided in Lemma F.1 Some steps this analysis are inspired by the
work of 34
Notation
Before proceeding, we need to define some useful quantities that will be employed throughout the proof.
27

---

Let us define vector Φ I$ of expected rewards. Its elements are such that:
((s) Σ rr(o)((o)s) r O-1ss.
(47)
From the quantity defined above, have that the expected reward given belief by at time & is: g(b,) = Σ (())b(()) = = b, = br.
(48)
SES
The real transition and observation model of the POMDP instance Q are defined respectively as T = aaa and O, We will use instead T, (Ta. and O to denote the transition model and observation models estimated by the Mixed Spectral astimation procedure at the beginning of episode 4, while we will use T2 [Te and O2 to denote the optimistic transition and observation model returned as output by the oracle and actually used during episode l. In a similar way, we will denote the estimated and optimistic POMDP instances at episode I with Qi and Qi respectively. We use p² to denote the optimal average reward for the optimistic POMDP Qt-
We introduce the deterministic function (b,, az Or+1) which returns the belief at the next step be41 given the action o, and the next observation Or-1 according to the Bayes' rule defined in ① We define similar function Hi a,, 01+1) which transforms the belief using the optimistic observation model Og and transition model Ta.,J used during the 1-th episode.
The probability distribution over the next observation 0++1 given belief b, and action is defined by:
P(or+1|be, a,) =,, CTT, by
where e, the standard basis vector in {0, 1) corresponding to observation E O. The probabilities here computed according to the transition model Ta, related to the chosen action and the observation model POMDP Q. With (((0++1bb,a)) we denote the anal- ogous probability computed using the observation and transition models of the optimistic POMDP Qi-
The same probability distribution holds over the next belief given the current belief, and it is defined as:
U(b++1|b, a.) Po(bu+1lb, a.) { (((o441lbs,a) if b H(b,, ag o), otherwise.
We will use Uj to denote similar measure defined with respect to the observation and transition models of the optimistic POMDP Q,
We will use E₁ to characterize the time intervals belonging to the I-th episode, from which we exclude the first and the last interval (this is done since the first and last samples of an interval are not used for SD). Hence, will have that the number of samples from the 1-th episode that will be used for SD is my Fal.
Having defined the employed notation, report here the statement of the theorem.
Theorem 6.2. Under Assumptions 4./ 4.2 and 6.1 let å E (0, 1/2). If the Mixed Spectral UCRL algorithm is run for a sufficiently large number of steps T, with probability at least 25, suffers regret bounded as:
D(SA)3/2
SAOT
RT
log?
(0())))))))))
where ((L) min (0)) and ç()) is defined as in Theorem 5.4 L= function appearing in Equation and is defined in Proposition G.1
D bounds the spar of the bias
Proof. Let recall here the definition of the regret as reported in 3
T-1
T-1
Rr Tp
Σ
r(o:)
Σ (p* (lr((:))
-
(49)
The span of the bias function is defined span(e) maxtes v(6) minses v(b).
28

---

where we consider an expectation E taken w.r.t. the true transition model T = Jael and the true observation model O as.A. The quantity Fr-1 denotes the filtration defined with respect to the events that occurred up to time 1 - 1. The second term in the summation defines martingale. Indeed, by denoting the stochastic process as:
Σ (B(r r(o:))
Xo X,
we observe that X₁ defines a martingale. By applying now the Azuma-Hoefiding inequality [4] with probability at least 1 6/4 we have:
(B(r(o))FFll - r(o,)) & /T log(/)).
(50)
We can further observe that since the belief b, is conditioned on the filtration Ft-1, we have:
B[r(o:)[Fr-I)
Σ b(())((s) g(b)),
SBS
where vector & is defined in Equation 447.. while function g is defined in Equation (48) We recall that the belief is computed using the true model parameters. Using analogous notation, we will denote the expected instantaneous reward assuming to have updated the belief using the optimistic transition model Ta, and observation model O2 as:
[((r()))) = r TT 62 g(b)).
From the quantities defined above, we can rewrite the first term of Equation (49 as:
T-1 (0
(p* - =
(51)
where we recall that the belief is updated using the actions taken by the played policy. By following the procedure described in the Mixed Spectral UCRL algorithm, at the beginning of each episode an optimistic POMDP Q is chosen from the set of possible POMDPs determined by the confidence region Cr(,t). We recall that the optimistic POMDP Qi is defined by the optimistic transition model T2 = {T J and the optimistic observation model Oy provided by the oracle. Since the bound for the estimated transition and observation models provided in Theorem 5.4 holds jointly with probability at least 1 - 3S Ab, we can also observe that P(Q E Ci())) > 1 3SAo Let consider two possible events: the good event which considers the case where for all episodes I, the true POMDP contained in the confidence sets (6)) and the failure event which denotes the complementary event.
By setting the confidence level used for the (-th episode di event can now be bounded as:
5
the probability of the failure
35A
1-1
Σ 3SA 5
L-1
P(Q & Ci())), for some 1) < Σ 3SA$
6,
(52)
3SA
From the result above, we can observe that the good event holds with probability at least 38. When this is the case, we have that pa = p' for any since the optimal average reward taken from the optimistic POMDP Q,
We now bound the regret under the good event during the different L episodes as:
Σ (p* g(be)) & 2L
Σ [-0
Σ 10
g(be))
T-
< 2L (To - 2) +
Σ (p' g((b))
re
4-1
2T + Σ
n
(a)
+
Σ
0'
m(bb)] + [(((tt) -b(b))
(53)
[-1
EE
(4)
29

---

where we have rewritten the summation by highlighting the different L episodes. In particular, for each episode we use interval E, that excludes the first and the last timestamp of that episode, while the term 2T. appearing in the first inequality is obtained by assuming to pay maximum regret for each pair of samples not contained in each Fq.
In the second inequality instead, we explicit the length To of the first episode for which we assume to pay maximum regret: the - term is due to the fact that the first and the last timestamps of the first episode are already counted in the 2L term. Finally, the last equality expresses the length of the first episode as the sum of the counts of the chosen actions, and adds and subtracts the quantity gi (bb) r G,b/.
For what will follow, we will focus on the term V
Analysis of (V)
Let us restate the term V defined above.
L-1
4-1 -
(V) =
d
a(t))] + [an(6)) - g0((i)
Σ
Σ IE
+
Σ EE
(r(())
g(bb)
F2
First Term
Sccond Term
(54)
We will now focus on analyzing the first and the second term separately.
Analysis of the First Term of Vi (line $4) Let us use the Bellman equation reported in Equation for the optimistic belief MDP, and the definition of the probability distribution U over the next belicf defined in the Notation section. The following relations hold:
I JnL.Ie va(be+1)Ui (d
o' + uy (b.) (i(b)) +
gi (b)) + (U7(-16,, at); o7())
The equation above allows us write that:
1-1
(p'
(n(b))))
(b)) at),, en(-))
1=1 E
Ee
Σ
Σ te
(-m(b)) + (U((),), + ax) - U(-1B,, az), 21 vn(-)))
a4) (b)
(55)
where the first equality is obtained from the Bellman Equation, while the last equality derives from adding and subtracting the term (U(-),, ax), o2()) for each time step We recall that U(-Ib/ ae) defines the probability distribution over the belief at the next step t + under the true POMDP instance Q, while Ui(- by, a.) represents this probability distribution under the optimistic instance Qt.
For the term (a) in 55
we have:
(a)
Σ
(-m((1)) + (U(-IB/,,.), v(()))
(56)
L-1
(b) o)((/+1)) + (-v((b(+)) + (U((IB,,,
leE)
Σ vi(lim)) + vr (b
Elur(() (n(b).1),
E
=
(a.1)
(a.2)
where the term (a.1) is obtained by observing that the sum on the first line reduces to a telescopic summation. For each episode 1, the terms appearing in this summation are respectively the difference between the value of the bias function of the belief in the first timestamp (denoted st) and the last plus one (denoted e + 1) timestamp appearing in E,
30

---

The term (a.2) is instead obtained by observing that:
(U(-)b), at), vx(-))
vi(dbe+1) )U dbb+1 1/, ae) El [00] (l
By using Proposition G.1
we can easily see that the span of the bias function defined as span(vi)
m (6)6) mintee ur(b) can be bounded by D/2 with D being a finite quantity. Hence, we can
write that:
1-1 Σ
L-1 - DL
(a.1)
vi((br)) + (1 &
(57)
For the term (a.2), we can observe that it defines a martingale. By applying analogous results as those used for bounding 50 we get with probability at least 5/4 that:
(a.2)
Σ
B( - (1(1)+)) & D 27
log log
(5)
4
(58)
EE
By combining the bounds for (a.1) and (a.2), we obtain with probability at least 1 6/4:
(a)
Σ (-v((t)) + (U(-)) ar). mn())) (I. (1-1)D DV BE
2T log
(59)
We can now proceed in bounding the term (b) appearing in 55 Let us recall the definition of the function H (br, ae, ot41) and P(oc+1lbe, ar) defined in the Notation section. The following relations hold:
(Ui(-1,, at) - U.IM/ (())))())))
(60)
vi(db' (i(lb (b11), unbb'U (bbl))
Σ 044160
vn (Hi(b), ar 0++1) Pi(or4illi, - Σ in (H(b,, at, P(oc+alby.
041100
Σ 001100
in Hi (H(b) ar, 0++1))] P(o+zlbb)))))))))
(b.1)
Σ Pr+150
(Hi ar 1)) [P] az) P(oc+1lb,
(b.2)
where in the first equality we have decoupled the stochasticity induced by the observation from the deterministic update of the belief I the next step through the H and Hi functions. Let analyze the different terms separately.
31

---

(b.1)
Σ 0r+150
ae (H, 22 (H(b), ar oc+1)) P P(ot+1lb/,a)
Σ
un (HilH, at, 0++1) - (H(1/ ar, o(+1)) P(ot+ilb),
Σ
Hi 04,0111) H( 01, 0+1)
P(ostaly/.
2
01110
(Holder's inequality and Proposition
G.1
D
Σ
C2
|
OfF C's (Ta, Ta. 1F)
P(or+1lb/, az) (Corollary H2
2
D
C2 0,
Cl Cs - Tallle)
(61)
The last inequality is instead obtained from Corollary F.2 which bounds the one-step error of the belief vector when updated using the estimated observation and transition matrices. Constants C2 and C3 are instead defined Lemma F. Concerning the term (b.2), we have:
(b.2)
Σ 01+150
(Hhlll) at or+1)) [P((04+166) P(oc+1|b a:)]
Σ 011100
1t (Hi(b), a, o.+1)) [R) P(o++1|b) at)]
D
Σ
P((o0+1b/,,a) as) P(oc+116),a))
(Proposition G.1
2
01-100
D
[(OrTT,, - OTT,)
D
NOTTOL. -OTT [b]l
2
D
(IO - TT2)ll + [(0; O)T,,
2
D
<
10/1/ - T4, || 04 11
(Def. of Matrix Norms)
2
D
||T To 11, + |0,
O|11 -01-))l1
(Since |O|]] and |T |l
2
D
||Ta.. Taelloo + |0, - -01]
2
D
V Ta, IF v0 0r 0|
2
By combining the results obtained for (b.1) and (b.2), we are able to bound the term (b) as:
D 4-1
(b) - 2 E
Σ
(C2+ (C)+v0) O + (Os + v5)[[Ta.. - -Tall)).
(62)
32

---

Finally, we can combine the results defined in lines 59 and 62 on (a) and (b) to finally bound the first
term of y (line 54 and obtain with probability least
0/4:
4 2)) ))+
Σ Σ (d' < D) D I=1 (EE)
2n
(63)
D レ-1
Σ
(C2 + vO) 0|r+ (C3 + IT) Ta,ll=)
D + vO) 4-1
< (L (L- D
2n
+
Σ
|0, - 0f|++
2
D + VS)
Σ
Σ
TTa.
Tale,
(64)
2
1-1
aEA
where we used that Er denotes the cardinality of the interval E,, and we also recall that ExEA 14
nt..
Analysis of the Second Term of v (line 54
We can now focus on the second term appearing the summation of 54
We have that:
Σ (b)) g(b,))
Σ Tot
T
E
||r 0016 -bbll
(| 1x <
te
||0,b| 0b, + 06, 0b1l
[10,-0001 1000 - be)l
||0] 111 |0 bela (Def. of Matrix Norms)
|00 041 || bel1
(Since |bb] and |O|| 1)
t
VolO,
O|F + ||b] - boll2
tEE
Volo, Ol + Σ
Σ |0
b,
1-1
FEE
Let consider the last term appearing in the last inequality. It can be bounded by using the result appearing in Lemma F.I In particular, we have:
4-1
Σ
Σ EE
bella &
C + C2 n2 Dr OlF + C3 Σ
| Tall
asA
33

---

with constants C1, C2 and C3 defined in Lemma F.1 From the results above, we obtain the following result for the second term of y
L-1
(an(b)) - s(b))) & (L - 1)C, + (C2 + 1)
nu - - O + C3
Σ
(a)
[
Tall
1=1
(65)
Merge of Obtained Results and Final Bound
Let us recall the definition of the regret in line 49 and let us observe that it can be bounded using the bound on the martingale in line and the bound on line 53 We have just seen how line 64 and 65 allow to bound the term V in 53 By combining everything, get:
T-1 Σ 1-0
Rr <
(p"
g(bi)) + v 27 log(4/8)
< 22 + Σ
T4
(a) 1)
4 2T log
+ D
2T log
4 (5)
aEA
D + v0)+ + 2(C2 11) 11
20s + D(Css + VS)
Σ
m
00 -0 +
Σ
ni
(a)
[Tat
TalF
2
1=1
2L
Σ
no
(a)
+(L ( 1) (D+
2T log 2
4
2T log
8
4
(c)
DC2vO
1-1
ni 00 0F
DCav S
(a)
(Ta. - TallF,
(66)
2
aE
(e)
Let us now focus the quantities appearing in (c) and (d). We have:
L-1
Co
SAllog(1O/6)
(c) + (d)
Σ
n
(a)
00 - O & n0
T1
Çayy
N₂
(Theorem 5.4
A
Co
SAI Lollog(35) (35
n1
(())
m
(From 35A
Co
3SAL 8
TM INI
SAL
(1))
max Ni)
(67)
Co
335L+
SAL log
(V2+ 1)/Nz
(1))
8
(Lemma
ColV2 + 1)
ASAL
SALT T log
(68)
((4)
where for the first term of the inequality on the first line we used E "o ni and Theorem 5.4
(a)
Here, we recall that Nj represents the number of samples used for the model estimation for the 1-th
34

---

episode. In line 67 we defined (()) = min ( while the last line simply follows by observing that NL & T.
We apply similar considerations to bound the term (e). In particular:
14
(a) (Ta
Fa
aEAA
C-S os(O)ç0)
Allog(1//6)
(a)
(Theorem 5.4
1=1
CrS
3SALOO
(0(
AL
n4
max 1, N (a)
(69)
GEA 1=0
11((2+11)
3SAL40
Ao
N/
(Lemma G.2
for each a)
(0(0)(())
aEA
C-5(v2+1)
3SAL*O
AL.
YNN
(Cauchy-Schwanl inequality)
(0())(
5
C S
3SAL40
LT
(70)
(0)(
where the last but one inequality follows by recalling that Ng. = Eae NY
From the result obtained in 68 and 70. rewrite the bound on the regret reported in line 66 as:
(
2T (
RT 2T. (I. (1 (D+ CD) +
2T
log log
3DVOC&Co 2((1)
3SSLAO 8
3DS3/2AC,6
3SALAO
SALTlog
LT
log log
(0)(0)
holding with probability at least 1 - 26, obtained by using union bound on the bound of the two martingales (each one holding with probability least 8/ and on the bound of the optimistic model which holds with probability at least 1 (3/2)5, as reported in Eq. (52).
The last step of the proof consists in observing that, for the stopping condition employed by the algorithm, the number of total episodes can be bounded as L & A log(T/ Finally, the regret expression can be simplified by highlighting the dependencies on the main terms as follows:
D(SA) ())))
SAOT 8
RT < O
TO log²
This final step concludes the proof.
D Auxiliary Results for the Proof of Theorem 5.4
In this section, we will provide auxiliary results required for the proof of Theorem 5.4 They are based on previous results on learning Hidden Markov Models (HMM) and POMDPS by II] and [3]. We carefully adapt the results to the Mixed Spectral Estimation strategy presented in Algorithm
Lemma D.1 (Error Bound of u2,s 1..1), Let ((aLL) be the second view estimated using Algorithm 1 ((a.L)
L-1 is used to interact with the environment, and let P2,s A(O) be when the set of policies (m)[=1)
its s-th colunn. If (y(a) satisfies the conditions in Equation (95 and (102) then with probability at
35

---

least 1 35, we have:
16EM ( (a.b)
|| 12,0
pla.e
Ts 351 (a.b))
(a.L) with MM defined as in Equation 98 of Lemma D.4
Proof. Let us recall that each column (o.L) of the second view matrix V,(a,L) (a.4) by inverting Equation (6) We can thus write the following:
22,0
can be obtained from
2,,
(a.L)
22,
(a.LL)
= K((4
((aL)))
13,
(a.L)
2,1
K
3,1
33.0
(71)
(a.L)
K(al))
(((aL))
(a.L)
2,1
P3,0
+
2
2
k((_L)
K k((aLl)
R(a
(a,L)
+
2,1
3,1
3,1
33,
+
2
+
K2
(a.L)
2,1
K
(a.L) 3,1
33,
(a.L)
(a.L)
3,a
(72)
The terms in 72 can be bounded by using i) Lemma D.3 for the concentration bound of empir-
ical estimates for K
(a.))
2 ii) Proposition
D.5 for (K(T")) - (g ( iii
Lemmal D.2 for pá,s P3,s
(a.L)
2 iv)
Kg L)
< 1. v)
(K(- < 1/oas {1/as(K, (((
3,1
and vi)
L)
M3,
$ 1. Thus we have:
(1.11 (.. 22, 112
8L log (2OL/0)
K ((a0))
)1 77)
N
2G
8L log (20L/5)
14c (4 (a.1) as as(K (a.1))
os (1 3,1
())
12
(1 - 77
N(a)
(6.(). (a.1.)
(1 (1.1))
holding with probability at least - 35. The last inequality follows from observing that each of the first two terms is & cM (a.L.)
/all)//s(/ ( (K((1)))
Lemma D.2 (Error Bound for p (.. Let V. be the third view estimated Algorithm I wwee (o.L)
the set {m) L-1 of policies is used interact with the environment, and let P3. A(O) be its 8-th
column. If (7(a) satisfies the condition in Equation (95) reported in Lemma D.4 then, with probability
at least 28, we have:
L..
(a.
& 14)
with e La.L) defined as in Equation
98 of Lemma D.4
Proof. The theoretical guarantees on the estimation quality of the third view (().L) are related the guarantees provided by Spectral Decomposition approaches.
In past works such as [ and 30). has been shown that among the different spectral algorithms, those relying tensor decomposition are more sample efficient, Our approach relies on the Robust Tensor Power (RTP) method presented in [ which applied to the symmetrized and whitened third- order moment tensor. We will now denote the steps required to transform the empirical estimates and
36

---

provide them to the RTP algorithm. The definition of some of the quantities that are used throughout this proof, together with the employed notation, is discussed in Section E
Let us consider now the empirical matrices and tensors (without symmetrization) defined as:
Ma
(a)
v1 x 02 (a.1)
(a.l) (a.1)
N(
M
()
(a)
E
01
(a.1) X
02 @ 03
(a.1
(73)
(a)
We observe that the definition of the non-symmetrized matrix (a.LL) coincides with the one of k(@.4) These non-symmetrized versions indeed differ from the symmetrized one M(a.L) and
M3 (a..) presented in Theorem 5.3
Using the multilinear map notation introduced in Section we define the symmetrized and whitened tensor (aaa..)) (w.((a)) w.la.)), w(aa))) E gxSSxx where w:(a.t) Ox w((a.) g0xs
and W. w.(.r)) E ROxS are the corresponding symmetrization srammctrzaaioonwhittnnnnn matrices for each of the tensor dimensions. By using Lemma D.4 it is possible to show that for sufficient number of samples N/O).
the error (f (a.L) on the estimated symmetrized and whitened tensor M (a.L) (Wl(.L), Whaa., Wa(..)) can be bounded with probability at least 6 as:
x(")
2/20 I-n
8T.
V Walann min- os(vaa.)))
2
(a,L) MM
+
(74)
(Vllen min, 0 (V
V
Wmin
La.L)
also observe that when sufficient number of samples No(e) is used, the estimation properties of the RTP method are guaranteed. In particular, us denote with (a.L) ,.((a)) SES the set of robust eigenvector/ccieevvale pairs provided as output by RTP. Then, (M3,s
From Lemma D.4
from [. with probability least 1 28 the following holds 14
M 4) (WW(a,)) w(a.)) w(a.)))
Σ seS
(a,L) We
83
55c (5.(a.L) (a.L)
(75)
86 (a.L)
L). 3.
1|2
(a(a.))
(((a & 5c (o.L)
(76)
w ((a,))
Let us now denote with E3
(a.L)
(
(a.I.)
23.s p the error of the s-th column of the third view
matrix Vi (a.
We recall that in order to obtain the estimate (a,L) from the corresponding robust eigenvec- ((),L)
f3,8
tor/eigenvalue pair (f4,, ,00 a(a.1) given as output by RTP, we have to de-whiten vector 13,, which can done by the following relation:
(a.L) = L) S
p3...
where defined B ROxS as the Moore Peoore-enrroee inverse of (W(a))) T
The equation above is obtained by inverting the first Equation appearing in (16),, which relates the robust eigenvec- tor/eigenvalue pair of the whitened tensor with that of the whitened counterpart.
We use symbol " to denote the non-symmetrized quantities M2 and Ma in order to distinguish them from the symmetrized ones M2 and Ms. "To be more precise, the statement refers to permutation of the found cigenvectorleigeavatue pairs satisfying the condition above. However, to avoid clutter, we consider that the bounds are defined for the correct permutation of these estimates.
37

---

Let us now analyze the enror Eg ()
3 La
|| | (a.L)
33, (a..1) 112
(77)
((a.L) B (....
- ((a 1) B 33,
()
(78)
(((,L)
B f3.
(1.1))
(((a) 1) B p + w(a.))
B 33.
a(a.L)
B
pss
(o.L)
(79)
(a L).
3,
B B +
B Wy
3.8
3,8
(80)
(a)
(b)
We can bound the error of each term separately. Let us start with (a). For the first term of (a), we have:
La..L)
Wss
13, 1
123,3
((a.)))
(L
(81)
L)
where the first equality follows from the fact that (). is a unit vector, while the last equality
follows from the definition in Equation (116) linking the original eigenvalue (fa.L) with the one of
the whitened tensor ((..L) For the second term of (a), have:
4| M (a.L) M 2
B
13
2
(82)
2
La w
min, (V 2
where the result directly follows from Equation
112 in Proposition D.8
Let us now consider the term (b). We have:
B L.) ((a.L) - ( ((a.L)
(b)
(83)
2
L) (a.L) - B(a.1) p/l..111
(84)
< (( (a.L) alad) (a.11)
P3. 23
M3.8
+ w
a(a. (a.L)
43,
Wg
M3,
L)
(85)
< ((.
13,0
+ [((.T) 8
-
3,,
(a.L)
(86)
2
& L))
8EM
5E (a.L)
(From results in Equation (76)
La
L)
13
(87)
where the inequality in line 84 follows from [B12 & 1. By combining the expressions in 81 82 and
87 with probability at least 25, we get:
M L)
M, (a.2) 1/2
113,5 P23,5112 &
min, as (v + 13e (a.L) & 14c
L)
w La
V w
(a.2) where the last inequality is obtained by observing that the first term of the summation is & EM This last expression completes the proof.
Lemma D.3 (Concentration Bounds for Covariance Matrices obtained from Multiple Policies). Let (x L-1 policies interact with a POMDP Q generating trajectories I' (f) Let Assump- tion 4.3 hold for each action E A and each policy क E P. Then, for any V E [1,2,3) and
+ v. with probability at least 1 - -. the following holds:
1
Σ
U
(a.))
U
(o.9
E
Σ T
u
(a,1)
(0,1)
8L log (20L/0) N (a)
0
7j
())
38

---

For the tensor case, for [V, .14 being any permutation of the set {1, 2, 3/, with probability at least
1 6, it holds:
1
(a.)) (a.) (a.3) Uutt
@ UUy @ V
-
Σ
(a.)) uut @
(a.))
u @
(a.3)
NL
1=0
Te
Te
G
8L. log (102 + O)
1 - 71
Ni
where G max G(TT)) and min (T.). Here, 1
G( is the geometric
te[o.1-1]
te[0,1-1]
ergodicity constant of the Markov Chain obtained from policy mi and (mm) < 1 represents the related contraction coefficient.
Proof. The proof of this lemma follows from standard concentration bounds HMM when adapted to the observations conditioned on a specific action a. Let us first observe that the covariance matrix obtained from policy Ny is exactly defined as:
K
(a.))
E
(a.l) (a.1) Uott
(88)
(a)
nl
and we can define an analogous quantity for the tensor case as:
k((a.)) uuuiuu
Σ NET
(a.1) vvtt Dui
(e,))
(a.1) 6.t
(89)
Tl
where recall that m((0) the error on the quantities defined above can be bounded as:
17(10 (
By applying Theorem 13 in 31, when single policy m is used,
[K R
G(m)
log (20/8)
1- (-))(m))
ni
KKo R(aad) va ao
G(
log ((02 0)/8)
1- (
n1(0)
with probability at least - 8. In this version of the proof, differently from what done in [3] bound the distance by assuming that the expectation defining both K <(a.0) and k((a.) is defined with respect to the initial (arbitrary) state distribution, which may be different from the stationary one
v."""
Since we assume have multiple policies interacting with the environment, our objective is to provide a bound for mixing covariance matrix and a mixing tensor, respectively denoted as:
L-1 nl
L-1
K
(a.L) v.
(a)
((dd)
E
(a.)) (a.) x
(90)
(1a)
(1))
0
IET
(c)
1-1
((a,L)
V.
=
((a)
Σ
(a)
K
(a.))
v.
((aa
Σ E
Σ
untt
(a.))
& w 8 2
(a.))
(91)
1-0
1-
(ET((
IIndeed, for Spectral decomposition techniques to be applied, it is not required that the moments are defined with respect the stationary state distribution.
39

---

We will study the error for the mixed covariance matrices. The same steps will hold for the tensor case. We have:
K La.L)
K
112
(a)
(K/
- R(aa)))
(92)
2,00
(a)
1
(a)
v.y'
R/aal 12
(Triangle Inequality)
Σ
11
(a)
G(T)) (7(())
log (20L/6)
(Union Bound)
NT. 1-0
1-
m
loo (2OL/6)
71
(a)
(93)
Nt
n2
(a)
δ
1
8log (20L/6)
(94)
77)
G
8L log (20L/8)
(Cauchy-Schwarz)
N/A
where in line 93 we use the new terms Ō max G(T)) and ij = min 7TT)). We finally 1=
[=
observe that the bound on the mixture covariance matrix presents a further term v L in the bound due to the application of the union bound. The final result follows by substituting the definition of the covariance matrix in the statement of the lemma.
D.1 Minimum Number of Samples Required for Applying Tensor Decomposition
Lemma D.4. Let M and M...L) be defined as in Equations 73 and 4.3 hold. Then, if the number of samples satisfies:
Let Assumptions 4./
4.2
2G -7)
2L +0)
N/O0
8L
Ω
(95)
(a.L) min
min, as( (VV(a..)))) 72
where
1/3
88
S
Ω max 1,
2,16 16
C
(a.L) win
min, (s(Vaaa
[a
then the following relation holds:
|M(a.L) M Ma & (1/2)os ((a.))..
(96)
Hence, this condition allows applying the RTP approach the estimated tensor ((a.)) (Wla..) W(o.)) W((.))) as prescribed Proposition D.8
40

---

Proof. We recall here the result in Proposition
D.8 which allows to provide bound on the Waa.h)
estimation emor MM
(a of matrix ()
W b)
We
(a.
We have:
M -M, (2))
3
2v2 M3 ((. - Maa (a))
(Valint) min os (V(
CM
(a.L)
(97)
(Wila (a min
miny as (V/(o.)))) 3
(a.L) V
min
10
2/20 I-n
(a.1)
min (s(Vaa))))
min
(98)
V Vola (a
min, as (V(aL))
V
(a.L) W
Second Term
First Tern
where this last inequality uses concentration results on the empirical estimates of M (..L) and M(a.L) (Lemma D.3). and holds with probability least 8.
In order to successfully apply the RTP method on the estimated tensor, the estimation error es should be reasonably small. In particular, the result in Equation (97) holds under the assumption that M(eL)
(a.L)
(
j (M, ()), as prescribed in Proposition D.8 In addition, from (2)
required that ii)
MM
LL.L)
for some constant C. From condition i), we require that: vs
2G/(1 7)
N/
87. log (40I/88,
(99)
(o.L)
min, os(via..)) 1
Winn
while for condition ii). it surely holds when each of the terms appearing in 98 is upper bounded by (2(2/S) under a suitable constant C, namely:
C
(First Term in 988
(Second Term in 98
2V5
2V
From the previous bounds, we obtain respectively:
4 22/(1 (1 - 77)
N(
>
8SL log (2 0)/8),
(100)
miny os (((V))))))) 13
C [
(a.L) w min
8G/(1-7)
No(0)
L (40L/8).
(101)
7/27 1/3
[C((((
(a,
min, os (v.
By rearranging the results reported in Equations 99
(100) and (101
we get the final result of the
lemma on the minimum number of samples required for the condition 96 hold.
41

---

D.2 Auxiliary Propositions
Proposition D.5. Let k(alt) be an empirical estimate of K31 (a.
obtained using No.0) samples. Then
if:
2
2
NO
8L log (20L/8).
(102)
)1 as (lla
?)
then with probability at least 1 - ô, the covariance matrix R(aa is invertible and holds that: 3,1
-1 (K
R(a
2G
18L log (20L/6)
3.1
$
(os(K((1L)
)"= (1- M
V
N (a)
Proof. Since Klo.))
21-0
nl
U/3
(a.))
x vs
(a.))
we can apply lemma D.3 and get
NE
K ()
[(a.1.)
G
8L log (20L/0)
3,1
$
17
(103)
Let us consider the condition:
( (K!4 -1
(a.2)
(a.L) 3,1
K3,
< 1/2.
(104)
2
By denoting with as( K (a.L)) the minimum singular value of matrix ((a.L) 3,1
we have
K (o.L) 1/os(K,)) (K( By using the bound in 103 it is easy to show that this con-
dition( (04) is verified with probability 1- - 8 when:
20
2
N(
8L log (20L/8).
(105)
ast K
(1
m
Under condition (104). we can state the following:
-1
K
(a,
K (a (.)
3,1
(K(a)) -1
(a.1))
K
$
(106)
L))
K (a.L)
1
3,1
3,1
3,1
< 2
K (a.L)
3,1
-1
K (a.L)
3,1
(a,L)
3,1
(107)
2
2G
8L log (20L/0)
(108)
0s
3.1
La.L)
(1
77)
N (a)
where line 106 derives from Lemma E,4 in 2 while line 107 is obtained by substituting at the denominator the condition in 104
Proposition D.6. (From 3) Let W XXX and W RYxX with V > X be any pair of matrices such that W W + for a suitable enror matrix E and let ax (W) be the X-th singular value of matrix W. If the error matrix is such that:
1112 & (x(W)
(109)
2
then we can derive the following:
1
21 &
$ (x(W)
ox(W)
42

---

Proof. Given that W is perturbation of the true matrix W, we can use Weyl inequality to have bound on the difference of the minimum singular value:
1ox xx( & W
W
which leads to
xx > xx xx W 22
Since we have assumed that the perturbation is not too large, we can safely invert this bound to obtain:
1
1
x (W) ox(W) W W
x (W)/2
where the last inequality follows from the precondition on the perturbation error (109 Hence, we can derive the final result as:
2 I ox(W) ox(W)
Proposition D.7. (From (22)) Let W and W be any pair of matrices such that W = W + E for suitable error matrix E. Then we have:
1+ v5
| - W1
max { 12, 1231 Fl2.
2
with || 1112 denoting the spectral norm.
Proposition D.8 (From (3). Ler M = E[ @ 2 and M₁ = Elu X U2
(a)] be
& Us the matrices associated with action A. with the expectations defined by policy πT P. Let also denote with M (W((), W:()) W(()) the symmetrized and whitened third-monee fird-moment tensor, as defined
in Section If Assumptiions 4.1 4.2 and 4.3 hold, then, under the condition
MM 1 < (1)))
(110)
the two following statements hold:
M (0) (w(a), whah wa(h) M3 (w (a)
(a) (a)))
EM =
3
M 0) Mig (3)
2 M M
(Valed ming (s((a
2
+
(111)
V (a)
3 min, os (Vs(aa)))
V
(1 (a)
M
M (1)) min, 0. (Vi(a)) 1
(wrdat) - -(17g%)
(17(o)
(
x
(112)
2
w min
E Symmetrization and Whitening
This section shows how the symmetrization and the whitening steps be used for the quantities defined in this work. To reduce clutter, we will avoid using the apices and L in this section.
Notation
We will stick here with the notation used in I. Let us denote p-th order tensor as A E X R".. When ni :ig np n, we can simply write A @PR" For a vector E B let use
The requirements the minimum number of samples needed to satisfy 110 reported in Lemma D.4
43

---

y v u X UEE " R" to denote its p-th order tensor. We can consider A be a multilinear map when it holds that for a of matrices (V; E Raxm; i
8"R"
[p]). the (61, ......................... 1 entry in of the tensor A(V,, V2,.... ,..,....... Vp) E R Xma Xxp is
[A(V1, V2,.... Vo) Ve
Σ
[Vl [V2l22.82 ... [Vplipnlp
So, a matrix (p= 2), then we have:
A(V, V2) V,T. AV2.
(113)
Symmetrization
Let us now denote with v1 RR,, 02 e Ieds and By E Rdds the three view vectors, and let V E Rd V2 e ddda and V3 Rdds be the associated view matrices, with k & dy for {1, 2,
We use Muyi to denote the i-th column of the view matrix V. Let us consider the second moment
M2 Rdixda and third moment M3 Rdd xdaxds of the three views follows:
M2 E 121
Σ
M1,1 & 22
Ms E
Σ wi M1s @ M2
M3,
(114)
Our objective is to represent these views as the second-order tensor and the third-order tensor with respect view U3. In order achieve this result, we need modify the views on and U2 by making use of the covariance matrices as follows:
1
K3,2 (K12)) 01
1
K3,1 (K2,1) 02
R
R
with R1 Rid xds and R2 R being the rotation matrices of the views d1 and v2 respectively. Using notation in Equation 113 it is possible to show that the symmetized version M2 e IR xdg can be defined as:
M2 = M2 R2) = RT M2 R₂ E Elvs
2 0zl = Σ
M3,1 @ p3.5.
Whitening
When the symmetrization step is concluded, the third-order matrix needs to be whitened in order to the Robust Tensor Power (RTP) method it. The whitening transformation is defined through the matrix W jddxk and is such that:
M2(W, W) = W M2W = I,
with M2 being the symmetrized matrix defined above and I E R is the identity matrix. From the relations above, we also have:
Mc(W, W) W M&W W R MrRoW Mr RiW,
R2W)
(115)
W,
W₂
which introduces the symmetrization setiiaattioowhhinninngg whitening matrices W1 IR xk and W2 E R Since the third view does not need to be symmetrized but only whitened, we have W3 W E Rd
Let us now define:
M3,, wwz W M4,.i
W
(116)
Vws
and we observe that:
k
M2(W,,W5) M2 W)
Σ WT (Warsess)) (WWiHas))) W
Σ
Pa. P3. =
In POMDP setting, we have di d2 ds O and k S.
44

---

from which we also observe that Pa,i E IR are orthonormal vectors. We can now define the symmetrized and whitened tensor M2 W2, W3) Bexaxk as:
Ma 22, W3) = Ma W, W) = Σ wi (W p3.1
33
We 3, (117)
where the first equality follows from analogous considerations those in Equation (15).
The decomposition expressed in the last equality allows representing tensor MM W2, Wa) in terms of the orthonormal eigenvectors faa, and the related eigenvalues Wj In this form, the tensor can be provided as input to the RTP method [. The RTP method will then provide as output an estimate of the robust cigenvectorreiggevvlle pairs (fa,, @.)) for each [A:]
Finally, the original eigenvectoor/iigcvaale pairs (1a Wi) can be recovered by inverting the Equa- tions in 116
F Belief Vector Concentration Bound
We present here Lemma F.1 that will be fundamental for proving the regret result of the Mixed Spectral UCRL algorithm.
Lemma F.1. Let be POMDP instance satisfying Assumption be the estimate of the observation and transition model and let T (or, at) be trajectory generated while interacting with the environment. We have that:
6. Let O and T (Ta)aEA
T E b.1l <Ch C2T Öf1F C3
Σn |Te
Talle,
where Ct C2 C3 are finite constants, while (a) represents the number of times each action E A chosen during the interaction.
Proof. We denote with b, and the estimated and real belief vector time updated using Equation using respectively the estimated and real transition model. From the belief decomposition reported in [10), we derive that the belief eтror bound time is:
Bo
bal2
4(1
6)
|
-TallF + v S0
10
Of
b. beli 4n
vSO
Co
(118)
where 1) = 1 - while co is finite constant based on both the transition and the observation model such that min min min Eves (s))s) which is always positive thanks to oEO sES
Assumption 6.1
proceed by bounding 118 as:
8n²
4
1-1
(-1 (I - ((alll)))l 4 AVS0(1
c)
18. bulla
Σ 1
Ole.
E
ECo
where the inequality simply follows by observing that 1ioo boll2
1io
boll 2
This bound shows that the error in the belief vector depends on sequence of actions and the contribution in the error of each action scales geometrically with time. Using the relations above, let
45

---

us now bound the sum of belief enrors over T + different time steps:
Σ b2 bella < 2+
Σ
8nf +
4(1 -) c)
1---1 (iTe, - -Tall +
2
2-0
1=0
4v 50(1 c)
1 11 -01
ECo
1=0
2
Σ
81j
4v 50(1 - 6)
Σ
1/ 1/11-110
0 +
ECo
f-1
1=0
(b)
+
4(1
c)
Σ
11
(
Ta.lF)
2
where the constant 2 is obtained by bounding the first term 1100 - bolli Let us now focus on the terms (a) and (b).
< 2.
T
(0) 2 8
Σ
17
2+
8
10
1
c
1-
c
1
(b) 4 - O
Σ
4v SO(( - <) - O|
T
CCo
CCo
1-
1=1--
Differently, the term can be bounded by using the result from 226 (see their Lemma D.1) and we obtain that:
(c) & 4(1-) c) (1 7) a6.A
Σ (a) [Ta - falF 4(1 - c)²
Σ n (
-TalF
asA
where (a) represents the number of times action a A is chosen during the interaction, while the last step follows by using the definition of
By combining the results in (a), (b) and (c), we get:
b
bell1
10
4VS0(1 - o]] OFF
1- +
T
4(1-)²²
Σ
(((a) IT.
Tall
CCo
3
1=U
aEA
10(1 -))
4v 4v 50 - 2) Oll
4(1 - c)2
Σ n
(a)
I - Ta-Tall
2 +
+
éco
3
aEA
(119)
where in the last line we simply substituted the definition of r) into the bound. The final result the lemma simply follows by defining the constants
10
4v
e)2
4(1-)²
C
C2
C3
(120)
ecoo
From the considerations reported above, can derive the following corollary for the one-step belief eтror.
Corollary F22. (One-step Belief Bound) Let be a POMDP instance satisfying Assumption 6. Let us denote with (O, T.) and (0, T.) respectively the real and estimated model parameters related to action Starting from common belief vector bo. and choosing action E A, the one-step error in the estimated belief vector can be bounded as:
- b1ll1 b
C2 1 OFF C's TT. -TaFF.
46

---

where constants C2 and C3 are defined in line 720
Proof. The proof of this corollary easily follows from the bound 118 by using t and having that by = by-
G Miscellanea of Useful Results
This section is devoted to the presentation of some useful results used throughout the work.
The first one is taken from 34 and relates the maximum span of the bias function span(u) with finite constant D.
Let us assume to have POMDP instance that can be rewritten as a belief MDP. If Assumption holdss then for p. satisfying the Bellman Equation 2). we have the span of the bias function span(e) m (bb) min u(b) is bounded by D(e), where:
Proposition G.1 (Uniform bound the bias span from 34
D(e)= a-ap + (1 + loga (2)0)
1 - 2x (0,
with
Hence, this proposition ensures that span(v) bounded by D (ee/2) for any bias functions associated with a belief MDP derived from POMDP instance Q.
This second result is used in the bound of Theorem 6.2
Lemma G.2 (Lemma 19 in [4 For any sequence of numbers , with 0 & & Yn and Y& max 1, - y:
yk
(V2+ Yn.
H Comparison with Related Literature
We provide here a detailed comparison of our Mixed Spectral UCRL with respect to the SEEU and the SM-UCRL algorithms tackling the infinite-horizon average reward setting (Section H.I). while we devote Section H.2 to a discussion on the differences of our formulation with respect to Maximum-Likelihow approaches typically used in episodic settings.
H.1 Comparison with Algorithms in the Infinite-horizon setting
We provide here a comparison in terms assumptions and theoretical guarantees of our Mi Xix Spectral UCRL algorithm with other algorithms in the literature that tackle this setting, Some key aspects are reported in Table In particular:
Comparison with SEEU (32.. Our approach strictly improves over the SEEU algorithm both in terms of assumptions and results. Indeed, unlike SEEU, our algorithm does not require an assumption on the minimum values of the observation model. Additionally, we introduce the sample reuse strategy for adaptive policies, leading to an improved sample efficiency which, together with more refined theoretical analysis, also translates to an improved regret bound with respect to the interaction horizon, from ((32/3) to Ö(VT).
Comparison with SM-UCRL 3 Similarly, we also make improvements over the SM-UCRL algorithm. Indeed, the SM-UCRL algorithm employs stochastic memoryless policies which are known to suffer linear regret when compared against the optimal POMDP policy. The employed policy class includes those policies for which each action can be chosen with minimum probability 0 at
47

---

every time step. By introducing our sample reuse strategy, we improve sample efficiency, and we are obliged to continuously choose every action since we can use those observed in the past, hence being able to eliminate stochastic policies and allowing for = O.
On the other hand, our approach employs the stronger class of belief-based policies. This comes at
the cost of requiring an assumption on the minimum value of the transition model (as also done in SEEU) in order to bound the error of the estimated belief vector, as explained in Section of the main paper.
Both SEEU and SM-UCRL subsume Assumption 4.3 We show here how both the SEEU and the SM-UCRL algorithms rely on assumptions that imply our Assumption 4.3 In particular:
the SEEU algorithm directly employs the one-step reachability assumption (our Assumption 6.1 for learnability. Differently, we use the weaker Assumption 4.3 for learning the model parameters, and then require the stronger one-step reachability assumption to ensure guarantees for the Mixed Spectral UCRL algorithm.
the SM-UCRL algorithn thm assumes standard ergodicity assumptions (not conditioned on action) but restricts to the class of stochastic policies (t > 0). Under this set of stochastic policies and the ergodicity assumption, the state-action distribution dx (s, a) always exists and satisfies (s, a) > 0 for any (s, a) E S x A. Consequently, the conditional state distribution ((,x) is always well-defined (since, under the considered policy class, di. (a) 0 for any A) and its elements are always strictly positive, hence satisfying Assumption 4.3
Finally, we remark that the set of Assumptions 4.1 and 4.3 employed in our work constitute the minimum working assumptions for learning in the infinite-horizon average-reward POMDP setting.
H.2
Comparison between Spectral Decomposition and Maximum-likelihod Approaches
Besides Spectral Decomposition techniques, other methods can be used for parameter estimation. Among the most common, we highlight those based on Maximum SintuumLLikelline Likelihood estimation mainly adopted in the episodic setting, such as the OOM-UCB [19 or the Optimistic-MLE 20 algorithms. We describe below the two key differences between these approaches:
MLE-based methods lack Estimation Guarantees for Latent Variable Models, differently
from Spectral Methods.
MLEE-based methods are not guaranteed to recover the original parameters (0, T) when estimating latent variable models, such as HMMs or POMDPs. In contrast, Spectral Decomposition methods provide sinite-sample guarantees for such models and represent the most computationally efficient methods for estimating such models. Notably, MLE-based approaches are used to learn an alternative POMDP parametrization known as the Observable Operator Model (OOM) for which finite-same sample guarantees Crucially, it is important to highlight that knowledge of the Observable Operators does not alone allow recovering the original POMDP parameters (O, T) for which instead different techniques (Spectral Decomposition) and further assumptions (invertibility of the transition matrices and ergodicity-like conditions) are needed to ensure estimation guarantees.
be derived by only employing the a-weakly revealing condition.
2. MI.E-based approaches typically addresses the finite-horizon setting, while our focus is on the infinite-horizon one.
The difference between the two settings also lies in the class of optimal policies. Indeed, while the best policy in the finite-horizon case depends on the sequence observations and actions of limited length (bounded by the episode length H) and does not rely on notion of belief state, the optimal policy for the fefnite-horizon case depends on maintaining and updating belief vector over the hidden states. Since belief updates rely on the Bayes' rule, which in turn requires estimates of both the observation and transition models, we need to use estimation methods with sinite-sample guarantees (such Spectral Methods) to recover the model parameters. This is in contrast to the Enite-horizon setting, where guarantees on the policy suboptimality can related the quality of OOM estimates.
48

---

I Discussion on Computational Complexity
We discuss here the computational complexity of the Mixed Spectral Estimation procedure. The computational complexity of this approach is comparable with the estimation approaches used both by SEEU and SM-UCRL since all of them rely on the underlying tensor decomposition. The overall computational complexity of the method scales as O(A max(O', S log S)), where:
The complexity scales linearly with the number of actions since SD is performed separately for each action E A,
The first term in the max arises from inverting the covariance matrices having order O appearing Equation
The second term comes from the RTP strategy introduced in [. which is used as a subroutine by the Mixed Spectral Estimation strategy. This method operates whitened three-order tenso 18 with dimension x Hence, each operation requires ((55) computations, and, assuming each eigenvector is computed from roughly O(S) initializations, with (log S) power iterations per initialization, the total time for obtaining the S different eigenvectooreigeenaaue pairs is O(S log S). Some optimization techniques can reduce this complexity to (SSt).
symmetric and
We refer to for more detailed discussion this matter.
J Additional Simulations and Simulation Details
This section provides details about the numerical simulations reported in the main paper. The simulations illustrated in this work have been rum on an 88 Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz CPUs with 94 GB of RAM. The code can be found at http://ggg..tacccc./aa////////// httpa//aw.....aaeeo/////eeeaeaaa
com
.git
Transition and Observation Model Generation. For the generation of the different POMDPs, we adopted similar approach the one followed in (25). The matrices of both the observation and transition models are randomly generated, and successive modifications are applied:
Transition model Ta: we set minimum value for each cell of the matrix that should be at least 1/(10S).
Observation model O: for each state, we define a subset observations that may observed with higher probability with respect to the others. This caveat improves the informativeness of the observation model, hence avoiding matrices with zero (or close to zero) minimum singular values.
J.1 Simulations on Estimation Error of the Mixed Spectral Estimation Algorithm
In this section, we report further experiments on estimation errors of POMDP instances of different sizes. In particular, we analyze the behavior of our estimation approach with both smaller and larger instances with respect to the one presented in the main paper. The results are presented in Figure and are expressed in terms of the Frobenius norm.
For the experiment on the left, measured the estimation error over 10 different episodes, each one having size 10 steps. Since the considered POMDP is smaller with respect to the others (S = 3, required to achieve good model estimates.
A = 2, O 5), fewer samples For the experiment on the right, we consider a larger POMDP instance (S = 5, A 5, 0 5) and we run our simulation across 30 episodes, each one of length 1.2 10 steps. As expected, the estimation process in this case has more noise, but decrease in the estimation error is evident across the different episodes.
How Policies Vary across Episodes. The change belief Selicf-policies across the different episodes is implemented in the following way.
See Appendix E for details.
49

---

0.6
Eatimation
0.2
0.5
2
10
10
20
30
T2 Num Episodes
Num Episodes
0
To
T2
To + T2
Figure 3: Frobenius norm of the estimation enror of two different POMDP instances. For the instance on the left we have 3, A 95 %.c.i.)
2, O 5, for the one on the right S 5, A
O (10 runs,
Regred (1n*)
10
Horizon (10")
SMUCRL
SEEU Mixed Spectral UCRL
Figure 4: Regret comparison POMDP with S 3, A 3, O 4 violating Assumption 6.1 (10 runs, 95 %...i).
(i) Each policy has an internal transition and observation model that it uses to update its belief. When the episode changes, change well these components. We remark that these models only used for the internal update the belief and are independent of the transition and observation model of the interacting POMDP instance.
(ii) Each policy has an internal vector r Rº of rewards associated to each observation. At each step, the chosen action is the one maximizing the expected reward in the next time step. When the episode changes, we change as well the internal reward vector r. As last point, in order to ensure enough exploration of all actions, the policy has minimum probability of choosing every action at each time step.
J.2 Simulations and Details Regret Experiments
For the experiments on the regret, we adopted the following hyperparameters for the different algorithms.
Mixed Spectral UCRL: length of initial episode To 3* 105:
SM-UCRL: length of initial episode To 10a minimum action probability = 0.02:
SEEU: length of exploration phase = 10 length of initial exploitation phase = 10 At each new episode the length of the exploitation phase computed as vi 72, as defined in the original work.
Concerning the computation of the optimal policy, for both the SEEU and the Mixed Spectral UCRL algorithm, we adopted the following approach. Since there is uncertainty in the model parameters, the Extended Value Iteration algorithm [14] should be used to find a robust policy. However, in practice, since we are in the POMDP setting, our approach consists sampling multiple POMDPs within the confidence region (ō)), discretize the belief space of each of the corresponding belief MDPs, find the corresponding best policy by using Value Iteration on each discretized MDP, and finally return the best among them. Similar approaches are also employed in (3. For the considered simulations,
50

---

we adopted discretization step size of 0.04.
Since the SM-UCRL algorithm relies on memoryless policies, we applied similar sampling procedure and then directly the Value Iteration algorithm, replacing the state space with the observation space.
By following the suggestions in 3 replaced the theoretical bounds with smaller values. This approach is commonly used in experimental comparisons in these settings and generally results in either regret with larger multiplicative constants guarantees holding with a lower probability.
Regret Experiment Violating Assumption 6.1 Our belief is that Assumption 6.1 can be relaxed in practice while still guaranteeing sublinear regret, however hard to remove it from a technical perspective.
To corroborate our intuition, we run new regret experiments on a POMDP instance that violates Assumption 6. The experimental results are shown in Figure and demonstrate how the tested algorithms (both our Mixed Spectral UCRL and SEEU) show regret results that align with their theoretical guarantees, hence showing robustness failure of this assumption.
51


Reviews:
[{"review_id": "Qhx53YeiGG", "reviewer": "Reviewer_EFjn", "summary": "This paper studies spectral learning methods for infinite-horizon average-reward POMDPs. The authors propose a new spectral estimation technique that can learn the POMDP model using samples collected from multiple policies, whereas previous methods require all samples to be drawn from a single policy. Building on this estimation method, they develop an online algorithm that achieves $\\mathcal{O}(\\sqrt{T})$ regret, supported by theoretical analysis. Numerical simulations are also conducted to demonstrate the effectiveness of the proposed algorithm.", "questions": "a. Can MLE-based POMDP learning algorithms, such as optimistic MLE, be applied to the infinite-horizon average reward POMDP setting? What are the advantages of spectral learning methods over MLE-based approaches in this setting?\n\nb. How is the confidence set constructed in Algorithm 2? Please provide more details.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\na. This paper proposes a new POMDP spectral learning algorithm that achieves $\\mathcal{O}(\\sqrt{T})$ regret, improving upon the previous $\\mathcal{O}(T^{2/3})$ rate, which is significant.\n\nb. The authors consider a broad and important class of policies, belief-based policies, which are more general and expressive than memoryless policies.\n\nc. Numerical simulations demonstrate that the proposed algorithm achieves lower estimation error and regret compared to existing approaches.\n\nd. The presentation is clear and easy to follow.\n\nWeaknesses:\n\na. The proposed algorithm relies on additional assumptions, such as Assumptions 4.2 and 6.1, which are not required in MLE-based methods for learning POMDPs. In particular, Assumption 6.1 appears quite strong and may not hold in practice.\n\nb. I am curious whether MLE-based methods, such as optimistic MLE, can be applied to the infinite-horizon average reward POMDP setting. If so, what assumptions are needed, and what regret bounds can be achieved? The authors should compare their spectral learning algorithm with such approaches and discuss its advantages.\n\nc. While Assumption 4.1 is commonly adopted in the POMDP literature, it remains relatively strong, as it requires that instantaneous observations contain sufficient information about the latent state. A weaker alternative is the multi-step revealing condition. Does the proposed analysis still hold under this weaker condition?", "was_revised": true, "final_justification": "I maintain my original positive score.", "rebuttal": "We thank the reviewer for their thoughtful review and we appreciate that they find our improvement in the regret result significant, as well as the paper clear and easy to follow.  \nIn the following, we address the concerns raised, explain the rationale behind our assumptions and clarify why these assumptions are not needed by the Optimistic MLE algorithm.  We will include these discussions in the final version of the work.\n\n---\n### Discussion on MLE-based methods and the Optimistic MLE Algorithm\n\nWe explain the key differences below:\n1. **MLE-based methods lack Estimation Guarantees for Latent Variable Models, differently from Spectral Methods**.  \nMLE-based methods are not guaranteed to recover the original parameters when estimating latent variable models such as HMM or POMDPs. In contrast, Spectral Decomposition methods provide finite-sample guarantees for such models and represent the most computationally efficient methods for estimating such models. Notably, MLE-based approaches are used to learn an alternative POMDP parametrization known as *Observable Operator Model* (OOM). See, for example, OOM-UCB [1] or Optimistic MLE [2]. Since these quantities can be estimated from data, learning them avoids any guesswork about the hidden states and thus allows for algorithms with strong guarantees of success.  \n**Crucially, there are no algorithms that allow recovering estimates of the original POMDP parameters $(\\mathbb{O}, \\mathbb{T})$ from the estimates of the *Observable Operator Model* (OOM)**.\n\n2. **The Optimistic MLE algorithm [2] addresses the finite-horizon setting, while we focus on the infinite-horizon one.**  \nThe difference between the two settings also lies in the class of optimal policies. Indeed, while the best policy in the finite-horizon case depends on the sequence of observations and actions of limited length (bounded by the episode length $H$) and does not rely on a notion of belief state, the optimal policy for the infinite-horizon case depends on maintaining and updating a belief vector over the hidden states. Since belief updates rely on the Bayes' rule, which in turn requires accurate estimates of both the observation and transition models, **we need to use estimation methods with finite sample guarantees (such as Spectral Methods) to recover the model parameters**. This is in contrast to the finite-horizon setting, where guarantees on the policy suboptimality can only depend on the quality of OOM estimates.\n\n---\n### Discussion on Assumptions \n1. **Invertibility of the Transition Matrices (Assumption 4.2).**  \nThis assumption is necessary to recover the original POMDP parameters, and is consistently used when learning Latent Variable Models [3,4,5,6]. **Without this assumption, it is information-theoretically impossible to recover the POMDP parameters** since there are cases where distributions induced from one state can be represented as a convex combination of some other state, making identifiability impossible [1].  \n**The invertibility assumption is not used in Optimistic MLE since, as discussed in the points above, this algorithm does not need to recover the original POMDP parameters**, but focuses on learning OOM for which the $\\alpha$-weakly revealing assumption on the observation model is sufficient alone for learning. \n\n2. **One-step Reachability (Assumption 6.1).**\n    - **Motivation.**  \nThis assumption is **standard when dealing with belief-based policies in the infinite-horizon setting**. We remark that it is **not required for model estimation** but is used only for the Mixed Spectral UCRL algorithm. It relates the belief error $\\|\\widehat{b}_t-b_t\\|_1$ with the estimated model error (see our Lemma F.1 for details). The origin behind this assumption lies in the **normalization step that appears in the Bayes' update rule**: assuming positive values for the transition matrix avoids divisions by zero. This issue has a long story and has been handled by never assigning zero probability to any event [7] or by assuming enough stochasticity in the environment [8, 9].\n**This assumption has been consistently used in subsequent works.** Some of them employed it in the easier bandit setting [6,10], while others [5,11] used this assumption with POMDPs. It is often used in conjunction with a minimum entry condition on the observation matrix [5,10].\n    - **Real-life Applicability.**  \nRather than complex physical systems where a given state may be reached only by a precise sequence of actions, **this assumption is commonly satisfied in problems modeling user or people behaviour**. POMDPs are indeed frequently used to model the hidden intent or preference of a user [12] or to define their health condition, such as in the context of medical diagnosis and decision support [13]. This assumption is also reasonable in problems with a limited state space, e.g., *bear market* and *bull market* in the financial domain [14].\n    - **Is Assumption 6.1 necessary?**  \nFirst of all, we remark that **this assumption is not employed by Optimistic MLE since belief-based policies are not required in the finite horizon setting**. Concerning our setting, this assumption seems difficult to relax from a technical point of view. However, **we believe that this assumption can be relaxed in practice** since it is reasonable to think that good model estimates lead to small belief errors, even when Assumption 6.1 is not satisfied.  \nTo corroborate our intuition, **we run new regret experiments on a POMDP instance that violates Assumption 6.1**. The experimental results are shown in the answer to Reviewer 2RDR. The simulations show how the tested algorithms present results that align with their theoretical guarantees, hence **showing robustness to failure of this assumption**. \n    \n3. **Relaxation of $\\alpha$-weakly Revealing Condition (Assumption 4.1).**  \nThe $\\alpha$-weakly revealing condition is crucial for avoiding pathological POMDP instances and has largely been used when providing positive results for learning POMDPs. **Without it, learning becomes computationally and statistically intractable** as the observations do not provide enough information to recover the underlying model [15].\nHowever, this condition can also be relaxed to the *m-step $\\alpha$-weakly revealing* [2] by assuming that $\\sigma_{S}(\\mathbb{M}) \\ge \\alpha$ with $\\mathbb{M} \\in \\mathbb{R}^{A^{m-1}O^m}$ and such that \n$$\n\\mathbb{M}\\_{(\\mathbf{a}, \\mathbf{o}), s} = \\mathbb{P}\\left(o_{t:t+m-1} = \\mathbf{o} \\mid s_t = s, a_{t:t+m-2} = \\mathbf{a} \\right).\n$$\nWe believe that **extending spectral approaches in this new setting is doable with minor modifications** to the estimation algorithm. \nHowever, since this condition allows identifiability only when all action sequences of length $m-1$ are taken, the estimation algorithm is forced to use a random policy for estimation. **Indeed, if adaptive policies are used, some action sequences may never be taken, hence preventing model estimation.**\nThis would lead to a regret minimization algorithm that alternates between purely explorative and purely exploitative phases, **leading to a final regret that scales with $\\mathcal{O}(T^{2/3})$.** This conclusion aligns with existing results on the *m-step weakly revealing* setting: [15] indeed present a lower bound (for finite-horizon problems) for the *m-step weakly revealing* setting scaling with $\\Omega(T^{2/3})$, hence showing that this setting is inherently more difficult than the *single-step weakly revealing*.\n\n---\n### Can MLE-based Methods be used in the Infinite-horizon Setting?\nBy summarizing the answers about the comparison of MLE-based approaches and the discussion on the assumptions, we conclude that, even by adding the assumptions on the invertibility of the transition matrix (necessary for model identifiability), **MLE-based approaches do not provide sufficient guarantees for estimation of the POMDP parameters, hence limiting their usability in the infinite-horizon setting**. Indeed, estimating Observable Operator Models using MLE-based methods is not sufficient since these estimates do not allow for the recovery of the original POMDP parameters that are required for the update of the belief. \n\n---\n### Construction of the Confidence Set in Algorithm 2\nThe confidence set constructed in Algorithm 2 uses the confidence level $\\delta_l:=\\delta/(3SAl^3)$ with $l$ being the episode counter. Given the model parameters estimated through our Mixed Spectral Estimation approach $(\\widehat{\\mathbb{O}}, \\\\{\\widehat{\\mathbb{T}}\\_a\\\\} \\_{a \\in \\mathcal{A}})$, **the confidence set $\\mathcal{C}\\_l(\\delta_l)$ contains all models $(\\bar{\\mathbb{O}}, \\\\{\\bar{\\mathbb{T}}\\_a\\\\}_{a \\in \\mathcal{A}})$ such that the Frobenious norm between the difference of observation matrices $\\bar{\\mathbb{O}} - \\widehat{\\mathbb{O}}$ and the Frobenious norm of the difference of each of the transition matrices $\\bar{\\mathbb{T}}_a - \\widehat{\\mathbb{T}}_a$ respect the confidence bounds described in Theorem 5.4 obtained by using the confidence level $\\delta_l$**.\n\n---\n### References\n**[1] Jin** et al. 2020  \n**[2] Liu** et al. 2022  \n**[3] Anandkumar** et al. 2014  \n**[4] Azizzadenesheli** et al. 2016  \n**[5] Xiong** et al. 2022  \n**[6] Zhou** et al. 2021  \n**[7] Eyal Even-Dar,**  Sham M. Kakade, and Yishay Mansour. The value of observation for monitoring dynamic systems. In IJCAI, 2007  \n**[8] Daniel Hsu,** Sham M. Kakade, and Tong Zhang. A Spectral Algorithm for Learning Hidden Markov Models, 2012  \n**[9] De Castro** et al. 2017  \n**[10] Jiang** et al. 2023  \n**[11] Russo** et al. 2025  \n**[12] Craig Boutilier**. A pomdp formulation of preference elicitation problems. In AAAI/IAAI, 2002  \n**[13] Christopher Amato** and Emma Brunskill. Diagnose and decide: An optimal Bayesian approach, 2012  \n**[14] M. Dai**, Q. Zhang, and Q. J. Zhu. Trend following trading under a regime switching model. SIAM Journal on Financial Mathematics, 2010  \n**[15] Fan Chen** et al. 2023"}, {"review_id": "nwHgUv7fl8", "reviewer": "Reviewer_2RDR", "summary": "The paper proposes a new spectral estimation procedure for infinite-horizon average-reward POMDPs, enabling parameter estimation from samples collected under multiple belief-based policies. The key technical contribution is the Mixed Spectral Estimation method, which generalizes prior multi-view tensor decomposition techniques to the setting where trajectories come from different policies. This estimation method is integrated into a UCRL-style algorithm, yielding the first  O(\\sqrt{T}) regret bound against optimal belief-based policies in this setting.", "questions": "The questions are mainly on assumptions. \n- The method relies on the one-step reachability assumption (Assumption 6.1). How realistic is this assumption in practical POMDP settings? Could this be relaxed in future work?\n- The paper assumes invertibility of the transition matrices (Assumption 4.2). Is this assumption critical for identifiability, or are there alternative conditions that could be considered?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- Addresses a known bottleneck in spectral POMDP learning: the need to collect data from a single policy or to reset frequently. The proposed method sidesteps this by enabling estimation from mixed-policy data.\n- Regret guarantees improve over prior work, both in theory (better scaling than SEEU) and in practice (empirical results show lower regret).\n- The theory is clean and carefully constructed, relying on standard assumptions (observability, invertibility, ergodicity) and extending existing SD techniques in a technically non-trivial way.\n- Sample efficiency is improved compared to existing methods, particularly due to the ability to reuse data across episodes.\n\n**Weaknesses**\n- Strong assumptions remain: full-rank observability, invertibility of each transition matrix, and one-step reachability. These are common but restrictive. It's not clear how robust the approach is when these fail.\n- Reliance on an optimization oracle for solving belief MDPs is a significant abstraction. While common in this line of work, it sidesteps the planning problem entirely.\n- Experiments are limited in scale. All evaluation is on small POMDPs. There’s no discussion of how the method scales to larger problems or continuous state/obs/action spaces.", "was_revised": true, "final_justification": "The main concerns were on the assumption they made.\nThey are clearly addressed by their rebuttal and I would maintain the score, recommending accept.", "rebuttal": "We thank the reviewer for their insightful feedback, and we are pleased that Reviewer 2RDR finds the proposed mixed-strategy technically non-trivial and the improved sample efficiency valuable.  \nIn the following, we will address all the points and questions raised in the comments.\n\n---\n### Discussion on the Assumptions \n1. **One-step Reachability (Assumption 6.1).**\n    - **Motivation.**   \nThis is a **standard assumption when dealing with belief-based policies in the infinite-horizon setting**. \nImportantly, we highlight that this assumption is only required for the Mixed Spectral UCRL algorithm and is instead not necessary for the Mixed Spectral Estimation procedure, unlike related works [1,2] that require the one-step reachability assumption for both estimation and regret minimization. This is mainly a technical assumption employed in our analysis to relate the belief error $\\|\\widehat{b}_t-b_t\\|_1$ with the estimated model error (see Lemma F.1 for details).\n    - **Real-life Applicability.**  \nRather than complex physical systems where a given state may be reached only by a precise sequence of actions, **this assumption is commonly satisfied in problems modeling user or people behaviour**. POMDPs are indeed frequently used to model the hidden intent or preference of a user [3] or to define their health condition, such as in the context of medical diagnosis and decision support [4]. This assumption is also reasonable in problems with a limited state space, e.g., *bear market* and *bull market* in the financial domain [5].\n    - **Could this assumption be relaxed in future works?**  \nFrom a technical perspective, this assumption seems not easy to relax. Indeed, the origin behind this assumption lies in the **normalization step that appears in the Bayes' update rule**: assuming positive values for the transition matrix avoids divisions by zero. Past works circumvented this problem by never assigning zero probability to any event [6] or by assuming enough stochasticity in the environment [7, 8]. More recent works made consistent use of this assumption both in the bandit [1,9] and in the POMDP setting [2,10].\n    Despite the difficulty of removing it, **we believe that this assumption can be relaxed in practice** since it is reasonable to think that a good model estimate will lead to accurate belief updates, even when Assumption 6.1 is not satisfied.  \nTo corroborate our intuition, **we run new regret experiments on a POMDP instance that violates Assumption 6.1**. The experimental results are shown at the end of this section and demonstrate how the tested algorithms (both our Mixed Spectral UCRL and SEEU) show regret results that align with their theoretical guarantees, hence **showing robustness to failure of this assumption**. \n\n2. **Invertibility of Transition Matrices (Assumption 4.2).**  \nThis invertibility assumption is necessary to recover the original POMDP parameters, and is consistently used when learning Latent Variable Models, such as HMMs and POMDPs [1,2,11,12]. **Without this assumption, it is information-theoretically impossible to recover the POMDP parameters** since there are cases where distributions induced from one state can be represented as a convex combination of some other state, making identifiability impossible [13].  \nTypically, **this assumption is not used in the finite-horizon setting since in these works the POMDP parameters are not estimated**. Indeed, to recover a near-optimal policy, it is sufficient to estimate alternative POMDP parametrizations known as *Observable Operator Models*, from which, however, it is not possible to recover the original POMDP parameters. \n\n3. **$\\alpha$-weakly Revealing Condition (Assumption 4.1).**  \nThe $\\alpha$-weakly revealing condition is crucial for avoiding pathological POMDP instances and has largely been used when providing positive results for learning POMDPs. **Without it, learning becomes computationally and statistically intractable**, as the observations do not provide enough information to recover the underlying model. Indeed, [14] provides some lower bounds for the POMDP setting, showing an inverse dependency of the $\\alpha$ parameter.  \n**We discuss how this *single-step weakly revealing* assumption can be relaxed to the *multi-step weakly revealing* assumption [15] in the answer provided to Reviewer EFjn**.\n\nNotably, we highlight that **state-of-the-art results for the infinite-horizon setting [2, 19] rely on this same set of assumptions or use even stronger ones**: [2] assumes minimum entries for the observation matrix, while [19] assumes having a consistent estimator of the POMDP parameters. Our contribution lies in *i*) **relaxing some of these assumptions** and in *ii*) **providing stronger regret results with respect to previous approaches**.  \nWe refer to **Table 1 in Appendix H** for a comparison in terms of assumptions and results with the related literature.\n\n---\n### Discussion on the Optimization Oracle\nWe agree with the reviewer that the planning problem is completely avoided. However, we would like to remark that this is a common problem when facing POMDPs. In particular, **the usage of an optimization oracle is a standard practice, in particular when the focus is on the statistical learning part** [16,17]. This assumption is commonly employed both in the infinite horizon setting where the POMDP is treated as a belief MDP [2,12,18] but also in the finite horizon setting such as in Optimistic MLE approaches [13,15] where the objective is to find among all the possible POMDPs in an $\\epsilon$-cover of the parameter space (which is exponential in the state, action and observation space) the one which maximizes the likelihood of some observed trajectories.  \n**We highlight that various approximation techniques exist for planning under Belief MDPs**. Most approaches involve discretizing the belief space, yielding a modified MDP on which standard value iteration (VI) can be applied. This is indeed the approach we implemented for our regret experiments. Furthermore, **asymptotic convergence results have been provided** showing that as the discretization gets finer, the computed solution converges to the optimal policy [19].\n\n---\n### Discussion on Scaling to Larger Problems\nThe focus of this work is on the tabular setting with finite states, actions, and observations. However, **our approach and analysis can be easily extended to handle continuous observation spaces**, since spectral methods can be adapted to such settings [11]. Differently, our approach requires states and actions to be finite, and we believe that a different approach should be employed to deal with settings with continuous states and actions.  \nIn terms of sample complexity, the dependence of our approach is polynomial both for the estimation and for the regret minimization algorithm. In particular, as shown in Theorem 5.4, the estimation guarantees scale as $\\mathcal{O}(S\\sqrt{A\\log O})$, while Theorem 6.3 shows that the dependency of the regret w.r.t. the Mixed Spectral UCRL algorithm is of the order $\\mathcal{O}((SA)^{3/2}\\sqrt{O}\\log(SAO))$. \nConcerning the computational complexity of the Mixed Spectral Estimation procedure, we discuss this point in Section H.2 of the Appendix. We show that **our procedure scales linearly with the number of actions and polynomially with the number of states and observations**. \n\n---\n### Discussion on the Size of the Experiments\nWe acknowledge that the size of the POMDPs employed in the experiments is limited. However, **we would like to stress that the size of the tested models is larger than those appearing in the related works**.  \nCrucially, we would like to highlight that **most works in this setting do not present any numerical experiments**. Examples of this type are works tackling the finite horizon setting [13,15,20]. Similarly, related works in the infinite-horizon setting either do not present numerical simulations [18] or present problems with $S=2$, $A=2$, and $O=2$ [1,2,12].  \nFinally, we highlight that in Appendix I, we show some simulations with a larger instance with respect to those presented in the main paper.\n\n---\n### Experiments violating Assumption 6.1\nExperiments are run on a POMDP with $S=3$, $A=3$, $O=4$, which violates Assumption 6.1.  \nWe show the cumulative regret scaled by $10^4$. 10 runs, 95% c.i.\n\n|Method/Num Samples ($10^5$)|2.00|4.00|6.00|8.00|\n|-|-|-|-|-|\n|MixedSpectralUCRL|0.88 (0.96, 0.80)|1.37 (1.54, 1.19)|2.32 (2.74, 1.90)|2.83 (3.45, 2.20)|\n|SEEU|1.44 (1.54, 1.35)|2.68 (2.86, 2.50)|3.72 (4.05, 3.39)|4.70 (5.25, 4.16)|\n|SMUCRL|1.73 (1.92, 1.53)|3.52 (3.74, 3.29)|5.15 (5.68, 4.61)|6.63 (7.32, 5.95)|\n\n\n---\n### References\n**[1] Zhou** et al. 2021  \n**[2] Xiong** et al. 2022  \n**[3] Craig Boutilier**. A pomdp formulation of preference elicitation problems. In AAAI/IAAI, 2002  \n**[4] Christopher Amato** and Emma Brunskill. Diagnose and decide: An optimal Bayesian approach, 2012  \n**[5] M. Dai**, Q. Zhang, and Q. J. Zhu. Trend following trading under a regime switching model. SIAM Journal on Financial Mathematics, 2010  \n**[6] Eyal Even-Dar,**  Sham M. Kakade, and Yishay Mansour. The value of observation for monitoring dynamic systems. In IJCAI, 2007  \n**[7] Daniel Hsu,** Sham M. Kakade, and Tong Zhang. A Spectral Algorithm for Learning Hidden Markov Models, 2012  \n**[8] De Castro** et al. 2017  \n**[9] Jiang** et al. 2023  \n**[10] Russo** et al. 2025  \n**[11] Anandkumar** et al. 2014  \n**[12] Azizzadenesheli** et al. 2016  \n**[13] Jin** et al. 2020  \n**[14] Chen** et al. 2023  \n**[15] Liu** et al. 2022  \n**[16] Akshay Krishnamurthy**, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. arXiv:1602.02722, 2016  \n**[17] Jeongyeol Kwon**, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. Reinforcement learning in reward-mixing mdps. arXiv:2110.03743, 2021  \n**[18] Jafarnia Jahromi** et al. 2022  \n**[19] Yu** et al. 2004  \n**[20] Guo** et al. 2016"}, {"review_id": "p6hcFDjZxp", "reviewer": "Reviewer_ah8G", "summary": "This paper addresses the challenge of learning in infinite-horizon average-reward Partially Observable Markov Decision Processes (POMDPs).  The authors propose Mixed Spectral Estimation, which generalizes SD techniques to support belief-based policies and allows sample reuse across multiple adaptive policies. This answers an open question about applying spectral methods to multi-policy data. Leveraging this, they introduce Mixed Spectral UCRL, a regret minimization algorithm that achieves $\\tilde{\\mathcal{O}}(\\sqrt{T})$ regret against the optimal belief-based policy—improving over the state-of-the-art $\\tilde{\\mathcal{O}}(T^{2/3})$ —without requiring full knowledge of transition/observation models. Theoretical guarantees are provided under standard assumptions ($\\alpha$-weakly revealing, invertible transitions, per-action ergodicity), and numerical experiments validate the approach.", "questions": "Oracle Assumption and Practicality: The paper assumes access to an optimization oracle for computing the optimal policy. Given the computational intractability of solving POMDPs, what are the practical implications of this assumption? Could the proposed algorithm be combined with approximate planning methods without significantly degrading the theoretical guarantees or empirical performance?\n\nRelaxation of Assumption 6.1: Assumption 6.1 is quite strong, requiring all transition probabilities to be strictly positive.Can the authors elaborate on the specific challenges or potential modifications to the theoretical analysis that would be required to relax this assumption? What might be the impact on the regret bound if this assumption is relaxed?\n\nComparison with Non-Spectral Methods: While the paper compares against other spectral methods (SM-UCRL, SEEU), a brief discussion or comparison with non-spectral, model-based, or model-free reinforcement learning algorithms for POMDPs, even if they have weaker theoretical guarantees, could provide a broader context of the algorithm's standing in the wider POMDP literature.\n\nGeneralizability to Other POMDP Structures/Settings: Can the proposed method be extended to other structures of POMDPs (e.g., $L$-decodable POMDPs, observable POMDPs) or more complex multi-agent settings such as partially observable Markov games? What modifications or additional assumptions would be necessary for such extensions?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe core contribution, Mixed Spectral Estimation, directly addresses a significant open problem: the ability to combine samples from multiple adaptive policies for spectral learning in POMDPs. This is a novel and highly impactful extension of existing spectral methods, which typically suffer from data inefficiency due to single-policy data requirements. \nThe paper provides rigorous finite-sample guarantees for the Mixed Spectral Estimation procedure. Furthermore, the Mixed Spectral UCRL algorithm achieves a state-of-the-art regret bound of $\\tilde{\\mathcal{O}}(\\sqrt{T})$, which enables more sample-efficient online POMDP learning. Experiments show reduced estimation error/regret vs. baselines.\n\nWeaknesses:\n\nAssumption Dependence: Assumption 6.1 is critical for regret analysis but restrictive (e.g., deterministic transitions violate it) and Assumption 4.2 may not hold in sparse-transition POMDPs. The authors mention relaxing this as future work, but it is a current limitation.\n\nPractical Scalability: Tensor decomposition  has polynomial complexity but may not scale to very large state/action spaces.\nBelief updates and planning oracle remain computationally challenging. Specifically, finding optimal policies in continuous belief-MDPs is computationally intractable in general. This makes the proposed algorithm more theoretical than directly deployable in scenarios without such an oracle.\n\nEmpirical Scope: Experiments use small POMDPs. Larger-scale validation is needed.", "was_revised": true, "final_justification": "I have gone over the replies of the authors. They have answered the questions to my satisfaction, and I maintain my positive score.", "rebuttal": "We thank the reviewer for their thoughtful review, and we appreciate that Reviewer ah8G finds our new sample-efficient extension of spectral methods novel and highly impactful.  \nIn the following, we address the concerns raised, discuss the reasons behind the assumptions, and compare our work with different methods and different settings. We will include these considerations in the final version of the work.\n\n---\n### Discussion on Assumptions\n1. **One-step Reachability (Assumption 6.1).**\n    - **Motivation.**  \nThis assumption is **standard when dealing with belief-based policies in the infinite-horizon setting**. We remark that it is **not required for model estimation** but is used only for the Mixed Spectral UCRL algorithm. It relates the belief error $\\|\\widehat{b}_t-b_t\\|_1$ with the estimated model error (see Lemma F.1 for details). The origin behind this assumption lies in the **normalization step that appears in the Bayes' update rule**: assuming positive values for the transition matrix avoids divisions by zero. Past works circumvented this problem by never assigning zero probability to any event [1] or by assuming enough stochasticity in the environment [2, 3]. More recent works made consistent use of this assumption both in the bandit [4,5] and in the POMDP setting [6,7]. \n    - **What might be the impact on the regret bound if this assumption is relaxed?**  \nFrom a technical perspective, this assumption seems not easy to relax. However, **we believe that it is still possible to remove it and keep a sublinear regret** since it is reasonable to think that good model estimates lead to accurate belief updates, even when Assumption 6.1 is not satisfied.  \nIt is not straightforward to foresee how the regret would change when removing this assumption. We believe that a completely different approach should be used, for example, somehow avoiding the use of belief-based policies.\n    - **Relaxation of Assumption 6.1 in Simulations.**  \nTo corroborate our intuition, **we run new regret experiments on a POMDP instance that violates Assumption 6.1**. The experimental results are shown in the answer to Reviewer 2RDR. The simulations show how the tested algorithms present results that align with their theoretical guarantees, hence **showing robustness to failure of this assumption**. \n\n2. **Invertibility of the Transition Matrices (Assumption 4.2).**  \nWe kindly refer to the answer to Reviewer 2RDR for a more detailed discussion on this aspect.\n\nNotably, we highlight that **state-of-the-art results for the infinite-horizon setting [6, 13] rely on this same set of assumptions or use even stronger ones**: [6] assumes minimum entries for the observation matrix, while [13] assumes having a consistent estimator of the POMDP parameters. Our contribution lies in *i*) **relaxing some of these assumptions** and in *ii*) **providing stronger regret results with respect to previous approaches**.  \nWe refer to **Table 1 in Appendix H** for a comparison in terms of assumptions and results with the related literature.\n\n---\n### Discussion on the Optimization Oracle\n1. **Standard Practice in POMDPs.**  \nWe would like to remark that the **usage of an optimization oracle is a standard practice, in particular when the focus is on the statistical learning part** [11,12]. This assumption is commonly employed both in the infinite horizon setting where the POMDP is treated as a belief MDP [6,9,13] but also in the finite horizon setting such as in Optimistic MLE approaches [10,14] where the objective is to find among all the possible POMDPs in an $\\epsilon$-cover of the parameter space (exponential in $S$, $A$ and $O$) the one which maximizes the likelihood of some observed trajectories. \n2. **Approximate Oracles and Implications.**  \nWe highlight that various approximation techniques exist for planning under **Belief MDPs**. Most approaches involve discretizing the belief space, yielding a modified MDP on which standard value iteration (VI) can be applied. This is indeed the approach we implemented for our regret experiments. **[15] provided asymptotic convergence results** showing that as the discretization gets finer, the computed solution converges to the optimal policy.\nFrom a theoretical perspective, if the oracle returns an $\\epsilon$-optimal policy, the final regret would have an additional term $\\epsilon T$. However, if the policy suboptimality scales as $\\epsilon \\le \\mathcal{O}(1/\\sqrt{T})$, then the final regret bound would still be sublinear with rate $\\mathcal{O}(\\sqrt{T})$.\n\n---\n### Discussion on the Size of the Experiments\nWe kindly refer to the answer to Reviewer 2RDR for a discussion on this aspect.\n\n---\n### Comparison with Non-Spectral Methods\n1. Most approaches tackling the POMDP setting are **model-based**. \n    - **Bayesian Approaches.**  \nThey have been used for solving POMDPs, but **no consistent estimation procedures have been provided** using Bayesian methods. As an example, [13] uses a Bayesian approach while interacting with the environment, but they assume to have a model estimator with convenient convergence guarantees. They provide a Bayesian regret bound of order $\\mathcal{O}(T^{2/3})$.\n    - **MLE-based Approaches.**  \nThe initial approaches for learning latent variable models relied on the MLE-based approaches (such as Expectation-Maximization), which, however **do not provide accuracy guarantees for estimating Latent Variable Models**. \n    MLE-based approaches have found interest recently in the finite-horizon setting, where they are used to learn alternative POMDP parametrizations known as *Observable Operators Models*. However, learning these models does not allow recovering the original POMDP parameters that are instead necessary in the infinite-horizon setting.\n    - **Method of Moments.**  \nThese approaches are the standard when learning POMDPs since **are able to obtain a global optimum with finite sample guarantees**. Indeed, our spectral procedure falls into this category: it exploits the second and third-order moments to retrieve the model parameters with polynomial dependency with respect to the model parameters.  \n\n2. **Model-free approaches have also been explored for the Partially Observable setting.**  \nRecently, [17] presents the first model-free action critic framework on a policy class that takes as input a fixed-length window of observations. They focus on the finite-horizon setting and provide PAC guarantees for their algorithm. Differently, [18] consider policy gradient methods to learn Markovian policies only based on the last observation in the episodic (discounted and undiscounted) case.  \n**We are instead not aware of model-free methods for the infinite-horizon partially observable setting.**\n\n---\n### Generalization to Other POMDP Settings\nBased on the assumptions of our work, our setting falls into the category of *$\\alpha$-weakly revealing* POMDPs. We discuss below the relation of our setting with some other settings. \n1. **Extension to Observable POMDPs.**  \nOur method can be directly applied to the observable POMDP setting. The $\\gamma$-observability condition requires that $\\|\\mathbb{O}(b - b')\\| \\ge \\gamma\\|b - b'\\|$ for any $b, b' \\in \\Delta(\\mathcal{S})$. It is possible to show that $\\frac{\\alpha}{\\sqrt{S}} \\le \\gamma \\le 4\\alpha\\sqrt{O}$, hence **these two conditions are equivalent up to a factor of at most $\\mathcal{O}(\\sqrt{O})$** (see Lemma 35 in [14]).\n\n2. **Extension to $L$-decodable POMDPs**.  \nOur setting is not directly comparable to the $L$-decodable POMDP setting as neither setting is a strict subset of the other.\nHowever, **a generalization of both settings is the *multi-step weakly revealing* case**, on which spectral methods can be applied. For the extension of our approach to the *multi-step weakly-revealing*, please refer to the answer to Reviewer EFjn.\n\n3. **Extension to Partially Observable Markov Games**.  \nThis setting is more complex than the one we considered due to the presence of multiple agents. Lately, some positive results have been obtained by using the weakly-revealing assumption on the joint observation matrix over all the agents [19]. This approach extends to the multi-agent case the considerations already developed for the single-agent setting when using MLE approaches for finite-horizon problems. We strongly believe that the sample-reuse strategy using spectral decomposition can be adapted to the multi-agent setting with infinite horizon. However, how this can be done and how the regret would scale in such a setting is difficult to say a priori. We leave it as an interesting future direction.\n\n---\n### References\n**[1] Eyal Even-Dar,**  Sham M. Kakade, and Yishay Mansour. The value of observation for monitoring dynamic systems. In IJCAI, 2007  \n**[2] Daniel Hsu,** Sham M. Kakade, and Tong Zhang. A Spectral Algorithm for Learning Hidden Markov Models, 2012  \n**[3] De Castro** et al. 2017  \n**[4] Zhou** et al. 2021  \n**[5] Jiang** et al. 2023  \n**[6] Xiong** et al. 2022  \n**[7] Russo** et al. 2025  \n**[8] Anandkumar** et al. 2014  \n**[9] Azizzadenesheli** et al. 2016  \n**[10] Jin** et al. 2020  \n**[11] Akshay Krishnamurthy**, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations, 2016    \n**[12] Jeongyeol Kwon**, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. Reinforcement learning in reward-mixing mdps, 2021  \n**[13] Jafarnia Jahromi** et al. 2022  \n**[14] Liu** et al. 2022  \n**[15] Yu** et al. 2004  \n**[16] Guo** et al. 2016  \n**[17] Masatoshi Uehara**, Ayush Sekhari, Jason D Lee, Nathan Kallus, Wen Sun. Provably efficient reinforcement learning in partially observable dynamical systems, NeurIPS 2022  \n**[18] Kamyar Azizzadenesheli**, Yisong Yue, Animashree Anandkumar. Policy gradient in partially observable environments: Approximation and convergence, 2018  \n**[19] Qinghua Liu**, Csaba Szepesvári, Chi Jin. Sample-Efficient Reinforcement Learning of Partially Observable Markov Games, 2022"}]

Author rebuttal:

Meta-review: This is a borderline paper. The work makes progress on spectral methods for learning POMDPs, extending on previous results by allowing for more complex data-collection policies than simple policies such as memoryless ones. The reviewers generally agree that the paper is well-executed and solid in its technical contents. There are, however, also general consensus that the paper adopts several strong assumptions, though they are relatively standard in this line of work, but this indeed limits the significance of the work.
Decision: Accept (poster)