arXiv:1611.03907v2 [] 19 Jun 2017

Reinforcement Learning in Rich-Observation MDPs
using Spectral Methods

Kamyar Azizzadenesheli
University of California, Irvine
kazizzad@uci.edu

Alessandro Lazaric
SequeL, INRIA Lille, France
alessandro.lazaric@inria.fr

Animashree Anandkumar
University of California, Irvine
a.anandkumar@uci.edu

Abstract
Designing effective exploration-exploitation algorithms in Markov decision processes (MDPs) with large state-action spaces is the main challenge in reinforcement learning (RL). In fact, the learning performance degrades with the number of
states and actions in the MDP. However, MDPs often exhibit a low-dimensional
latent structure in practice, where a small hidden state is observable through a
possibly large number of observations. In this paper, we study the setting of
rich-observation Markov decision processes (ROMDP), where hidden states are
mapped to observations through an injective mapping, so that an observation can
be generated by only one hidden state. While this mapping is unknown a priori,
we introduce a spectral decomposition method that consistently estimates how
observations are clustered in the hidden states. The estimated clustering is then
integrated into an optimistic algorithm for RL (UCRL), which operates on the
smaller clustered space. The resulting algorithm proceeds through phases and we
show that its per-step regret (i.e., the difference in cumulative reward between the
algorithm and the optimal policy) decreases as more observations are clustered
together and finally matches the (ideal) performance of an RL algorithm running
directly on the hidden MDP.

1 Introduction
Reinforcement learning (RL) framework studies the agent-environment interaction, in which the
agent learns to maximize a given reward function in the long run [6, 23]. At the beginning of
the interaction, the agent is uncertain about the environment’s dynamics and must explore different
policies in order to gain information about it. Once the agent is fairly certain, the knowledge about
the environment can be exploited to compute a good policy attaining a large cumulative reward.
Designing algorithms that achieve an effective trade-off between exploration and exploitation is the
primary goal of reinforcement learning. The trade-off is commonly measured in terms of cumulative
regret, that is the difference between the rewards accumulated by the optimal policy (which requires
exact knowledge of the environment) and those obtained by the learning algorithm.
In practice, we often deal with environments with large observation spaces (e.g., robotics). In this
case the regret tends to be very large as it increases with the size of the observations. Nonetheless,
in many domains there is an underlying low dimensional latent space that summarizes the large
observation space and its dynamics and rewards (e.g., in robot navigation high-dimensional visual
and sensory input can be summarized in 2D as locations). If the mapping between the latent states
and the observations is known a priori, then it is trivial to exploit it and design a learning algorithm
that operates on the low-dimensional latent space rather than the large observation space. However,
this mapping is typically unknown and needs to be learnt by the agent. It is then crucial to develop

efficient learning algorithms that can quickly discover the mapping between hidden and observation
states and fully exploit the small size of the hidden space.
Contributions. In this paper we focus on rich-observation Markov decision processes (ROMDP),
where a small number of X hidden states are mapped to a large number of Y observations through
an injective mapping, so that an observation can be generated by only one hidden state and hidden
states can be viewed as clusters. If the mapping was known, one could directly run, e.g., UCRL and
obtained a regret scaling only with the number of hidden states
of observa√ X instead of the number
√
e Y Y N ) down to O(D
e X X N ), where D is
tions. More formally, the regret is reduced from O(D
the diameter of the MDP (i.e., the longest shortest path between any two observations/states) and N
is the total number of steps over which the regret is cumulated.
In this setting, we show that it is indeed possible to devise an algorithm that starting from observations can progressively cluster them in “smaller” states and eventually converge to the hidden MDP.
We introduce SL-UC, where we integrate spectral decomposition methods into the upper-bound for
RL algorithm (UCRL) [13]. The algorithm proceeds in epochs in which an estimated mapping between observations and hidden state is computed and an optimistic policy is computed on the MDP
(called auxiliary MDP) constructed from the samples collected so far and the estimated mapping.
The mapping is computed using spectral decomposition of the tensor associated to the observation
process. We prove that this method is guaranteed to correctly “cluster” observations together with
high probability. As a result, the dimensionality of the auxiliary MDP decreases as more observations are clustered, thus making the algorithm more efficient computationally and more effective
in finding good policies. Under suitable assumptions, we derive a regret bound showing that the
per-step regret decreases over epochs and we prove a worst-case bound on the number of steps (and
corresponding regret) before the full mapping between states and observations is computed. The regret cumulated over this period is actually constant as the time to correct clustering does not increase
with the number of steps N . As a result, we have that SL-UC asymptotically matches the regret of
learning directly on the latent MDP. We also notice that the improvement in the regret comes with
an equivalent reduction in time and space complexity. In fact, as more observations are clustered,
the space to store the auxiliary MDP decreases and the complexity of the extended value iteration
step in UCRL decreases from O(Y 3 ) down to O(X 3 ).
Related work. The assumption of the existence of a latent space is often used to reduce the learning
complexity. For multi-armed bandits, Gheshlaghi-Azar et al. [10] and Maillard and Mannor [19]
assume that a bandit problem is generated from an unknown (latent) finite set and show how the
regret can be significantly reduced by learning this set. Gentile et al. [9] consider the more general
scenario of latent contextual bandits, where the contexts belong to a few underlying hidden classes.
They show that a uniform exploration strategy over the contexts, combined with an online clustering
algorithm achieve a regret scaling only with the number of hidden clusters. An extension to recommender systems is considered in [11] where the contexts for the users and items are unknown a
priori. Again, uniform exploration is used together with the spectral algorithm of Anandkumar et al.
[1] to learn the latent classes.
The ROMDP model considered is a generalization of the latent contextual bandits, where actions influence the contexts (i.e., the states) and the objective is to maximize the long-term reward. ROMDPs
have been studied in [16] in the PAC-MDP setting and episodic deterministic environments using
an algorithm searching the best Q-function in a given function space. This result is extended to the
general class of contextual decision processes in [14]. Ortner [21] proposes an algorithm integrating
state aggregation with UCRL but, while the resulting algorithm may significantly reduce the computational complexity of UCRL, the analysis does not show any improvement in the regret. Finally, we
notice that ROMDPs are a special class of partially observable MDPs (POMDP). Azizzadenesheli
et al. [4] recently proposed an algorithm that leverages
√ spectral methods to learn the hidden dynamic of POMDPs and derived a regret scaling as Y using fully stochastic policies (which are
sub-optimal in ROMDPs). While the computation of the optimal memoryless policy relies on an
optimization oracle, which in general is NP-hard [3, 18], computing the optimal policy in ROMDPs
amounts to solving a standard MDP. Finally, Guo et al. [12] develops a PAC-MDP analysis for
learning in episodic POMDPs and obtain a bound that depends on the size of the observations.

2

y1

y1

a1

y2

y2

a2

y3

y3

y4

y4

y5

y5

y6

y6

y7

y7

y8

y8

a3

π

y9

y9

y10

y10

y11

y11
x1 x2 x3 x4

x1 x2 x3 x4

Figure 1: (left) Graphical model of a ROMDP. (middle) Example of an observation matrix O. Since state and
observation labelling is arbitrary, we arranged the non-zero values so as to display a diagonal structure. (right)
(a )
Example of clustering that can be achieved by policy π (e.g., Xπ 1 = {x2 , x3 }). Using each action we can
recover partial clusterings corresponding to 7 auxiliary states S = {s1 ..s7 } with clusters Ys1 = {y1 , y2 }
Ys2 = {y3 , y4 , y5 }, and Ys8 = {y10 , y11 }, while the remaining elements are the singletons y6 , y7 , y8 , and y9 .

2 Rich Observation MDPs
A rich-observation MDP (ROMDP) (Fig. 1(left)) is a tuple M = hX , Y, A, R, fT , fO i, where X , Y,
and A are the sets of hidden states, observations, and actions. We denote by X, Y , A their cardinality
and we enumerate their elements by i ∈ [X] = {1..X}, j ∈ [Y ] = {1..Y }, l ∈ [A] = {1..A}. We
assume that the hidden states are much fewer than the observations, i.e., X ≪ Y . We consider
rewards bounded in [0, 1] that depend only on hidden states and actions with a reward matrix R ∈
RA×X such that [R]i,l = E[r(x = i, a = l)]. The dynamics of the MDP is defined on the hidden
states as Ti′ ,i,l := fT (i′ |i, l) = P(x′ = i′ |x = i, a = l), where T ∈ RX×X×A is the transition tensor.
The observations are generated as [O]j,i = fO (j|i) = P(y = j|x = i), where the observation matrix
O ∈ RY ×X has minimum non-zero entry Omin . This model is a strict subset of POMDPs since each
observation y can be generated by only one hidden state (see Fig. 1-middle) and thus X can be seen
as a non-overlapping clustering of the observations.
We denote by Yx = Yi = {y = j ∈ Y : [O]j,i > 0} the set of observations in cluster x, while xy =
xj is the cluster observation y = j belongs to.1 This structure implies the existence of an observable
MDP MY = hY, A, R′ , fT′ i, where R′ = R as the reward of an observation-action pair (y, a) is the
same as in the hidden state-action pair (xy , a), and the dynamics can be obtained as fT′ (j ′ |j, a) =
P(y ′ = j ′ |y = j, a = l) = P(y ′ = j ′ |x′ = xj ′ )P(x′ = xj ′ |x = xj , a = l) = [O]j ′ ,xj′ [T ]xj′ ,xj ,l . We
measure the performance of an observation-based policy πY : Y → A starting from ahidden state
PN
x by its asymptotic average reward ρ(x; πY ) = limN →∞ E
t=1 rt /N x0 = x, πY . Given the
mapping between the ROMDP to the hidden MDP, the optimal policy πY∗ (y) is equal to the optimal
∗
hidden-state policy πX
: X → A for all y ∈ Yx . The learning performance of an algorithm run over
N steps is measured by the regret
RN = N ρ∗ −

N
X

∗
).
rt , where ρ∗ = ρ(πX
t=1

Finally we recall that the diameter
of the observation MDP is defined as DY =

maxy,y′ ∈Y minπ:Y→A E τπ (y, y ′ ) , where τπ (y, y ′ ) is the (random) number of steps from y to y ′
by following the observation-based policy π (similar for the diameter of the hidden MDP).

3 ROMDP Recovery Through Spectral Methods
In this section we introduce the spectral method used to to learn the structure of the observation matrix O. In particular, we show that we do not need to estimate O exactly as the clusters {Yx }x∈X can
be recovered by identifying the non-zero entries of O. We need a first assumption on the ROMDP.
Assumption 1. The Markov chain induced on the hidden MDP M by any policy πY is ergodic.
Under this assumption for any policy π there is a stationary distribution over hidden states ωπ and
(l)
(l)
a stationary distribution conditional on an action ωπ (i) = Pπ (x = i|a = l). Let Xπ = {i ∈ [X] :
1

Throughout the paper we use the indices i, j, and l and the “symbolic” values x, y, and a interchangeably.

3

(l)

ωπ (i) > 0} be the hidden states where action l could be taken according to policy π. In other
(l)
words, if Yπ = {j ∈ [Y ] : π(j) = l} is the set of observations in which policy π takes action l,
(l)
(l)
then Xπ is the set of hidden states {xy } with y ∈ Yπ (see Fig. 1-right). We also define the set of
(l)
all hidden states that can be reached starting from states in Xπ and taking action l, that is
o
[n

(l)
Xπ =
i′ ∈ [X] : P x′ = i′ |x = i, a = l > 0 .
(l)

i∈Xπ

(l)

Similarly X (l)
π is the set of hidden states from which we can achieve the states Xπ by policy π. We
need the following assumption.
Assumption 2 (Full-Rank). Given any action l, the slice of transition tensor [T ]·,·,l is full rank.
(l)

(l)

Asm. 2 implies that for any action l the dynamics of M is “expansive”, i.e., |Xπ | ≤ |X π |. In other
(l)
words, the number of hidden states where policy π can take an action l (i.e., Xπ ) is smaller than
(l)
the number of states that can be reached when executing action l itself (i.e., X π ).

Multi-view model and exact recovery. We are now ready to introduce the multi-view model [1]
that allows us to reconstruct the clustering structure of the ROMDP. We consider the trajectory
of observations and actions generated by an arbitrary policy π and we focus on three consecutive
observations yt−1 , yt , yt+1 at any step t. As customary in multi-view models, we vectorize the
observations into three one-hot view vectors ~v1 , ~v2 , ~v3 in {0, 1}Y such that ~v1 = ~ej means that the
observation in the first view is j ∈ [Y ] and where we remap time indices t − 1, t, t + 1 onto 1, 2,
and 3. We notice that these views are indeed independent random variables when conditioning on
the state x2 (i.e., the hidden state at time t) and the action a2 (i.e., the action at time t), thus defining
(l)
(l)
a multi-view model for the hidden state process. Let k1 = |X (l)
π |, k2 = |Xπ | and k3 = |X π |, then
(l)
(l)
(l)
we define the factor matrices V1 ∈ RY ×k1 , V2 ∈ RY ×k2 , V3 ∈ RY ×k3 as follows
(l)

(l)
[Vp(l) ]j,i = P(~vp = ~ej |x2 = i, a2 = l), with i ∈ X (l)
π for p = 1, i ∈ Xπ for p = 2, i ∈ X π for p = 3.
(l)

We are interested in estimating V2
(l)

[V2 ]j,i =

since it directly relates to the observation matrix as

P(a2 = l|y2 = j)P(y2 = j|x2 = i)
I{π(j) = l}fO (j|i)
=
,
P(a2 = l|x2 = i)
P(a2 = l|x2 = i)

(1)

(l)

where I is the indicator function. As it can be noticed, V2 borrows the same structure as
the observation matrix O and since we want to recover only the clustering structure of M (i.e.,
(l)
{Yi }i∈[X] ), it is sufficient to compute the columns of V2 up to any multiplicative constant. In
(l)

fact, any non-zero entry of V2 corresponds to a non-zero element in the original observation
(l)
matrix (i.e., [V2 ]j,i > 0 ⇒ [O]j,i > 0) and for any hidden state i, we can construct a cluster
(l)
(l)
Yi = {j ∈ [Y ] : [V2 ]j,i > 0}, which is accurate up to a re-labelling of the states. More formally,
(l)
there exists a mapping function σ (l) : X → X such that any pair of observations j, j ′ ∈ Yi is
′
such that j, j ∈ Yσ(i) . Nonetheless, as illustrated in Fig. 1-right, the clustering may not be minimal.
(l)

(l)

In fact, we have [O]j,i > 0 6⇒ [V2 ]j,i > 0 since [V2 ]j,i may be zero because of policy π, even
if [O]j,i > 0. Since the (unknown) mapping function σ (l) changes with actions, we are unable to
correctly “align” the clusters and we may obtain more clusters than hidden states. We define S as
the auxiliary state space obtained by the partial aggregation and we prove the following result.
(l)

(l)

Lemma 1. Given a policy π, for any action l and any hidden state i ∈ Xπ , let Yi be the observaS
(l)
(l)
tions that can be clustered together according to V2 and Y c = Y \ i,l Yi be the observations not
S
(l)
clustered, then the auxiliary state space S contains all the clusters { i,l Yi } and the singletons in
c
Y for a total number of elements S = |S| ≤ AX.
(l)

We now show how to recover the factor matrix V2 . We introduce mixed second and third order
(l)
(l)
moments as Kp,q = E[~vp ⊗ ~vq ], Kp,q,r = E[~vp ⊗ ~vq ⊗ ~vr ] where p, q, r is any permutation of
{1, 2, 3}. Exploiting the conditional independence of the views, the second moments can be written
P
(l)
(l)
(l)
(l)
(l)
(l)
as Kp,q = i∈X l ωπ (i)[Vp ]:,i ⊗ [Vq ]:,i where [Vp ]:,i is the i-th column of Vp . In general the
π

4

Algorithm 2 Spectral-Learning UCRL(SL-UC).

Algorithm 1 Spectral learning algorithm.

Initialize: t = 1, initial state x1 , k = 1, δ/N 6
While t < N do
Run Alg. 1 on samples from epoch k − 1 and obtain
Sb
Compute aux. space Sb(k) by merging Sb and Sb(k−1)

Input: Trajectory (y1 , a1 , . . . , yN )
For Action l ∈ [A] do
b (l) , K
b (l) , K
b (l) , and K
b (l)
Estimate second moments K
2,3
1,3
2,1
3,1
(l)
b (see App. B)
Estimate the rank of matrix K
2,3
Compute symmetrized views e
v1,t and ve3,t , for t =
2..N − 2
c(l)
c(l) and M
Compute second and third moments M
3
2
(l)
b
Compute V2 from the tensor decomposition of (an
c(l)
orthogonalized version of) M

Compute the estimate reward r (k) and dynamics p(k)
Construct admissible AuxMDPs M(k)
Compute the optimistic policy
π
e (k) = arg max max ρ(π; M )
(6)
π

3

M ∈M(k)

Set v (s, l) = 0 for all actions l ∈ A, s ∈ Sb(k)
While ∀l, ∀s, v (k) (s, l) < max{1, N (k) (s, l)} do
Execute at = π
e (k) (st )
Observe reward rt and observation yt
(k)

return clusters
(l)
(l)
Ybi = {j ∈ [Y ] : [Ve2 ]j,i > 0}

(l)

second moment matrices are rank deficient, with rank Xπ . We can construct a symmetric second
moment by introducing the symmetrized views
(l)

(l)

(l)

ve1 = K2,3 (K1,3 )†~v1 ,

(l)

ve3 = K2,1 (K3,1 )†~v3 ,

(2)

where K † denotes the pseudoinverse. Then we can construct the second and third moments as

 X (l)
(l)
(l)
(l)
M2 = E ve1 ⊗ ve3 =
ωπ (i)[V2 ]:,i ⊗ [V2 ]:,i .
(3)
(l)

i∈Xπ

(l)

M3

X


(l)
(l)
(l)
= E ve1 ⊗ ve3 ⊗ ~v2 =
ωπ(l) (i)[V2 ]:,i ⊗ [V2 ]:,i ⊗ [V2 ]:,i .

(4)

i∈Xπl

We can now employ the standard machinery of tensor decomposition methods to orthogonalize the
(l)
(l)
(l)
tensor M3 using M2 and recover V2 (refer to [1] for further details) and a suitable clustering.
(l)

Lemma 2. For any action l ∈ [A], let M3 be the third moment constructed on the symmetrized
(l)
views as in Eq. 4, then we can orthogonalize it using the second moment M2 and obtain a unique
(l)
spectral decomposition from which we compute the exact factor matrix [V2 ]j,i . As a result, for any
(l)
(l)
hidden state i ∈ Xπ we define the cluster Yei as
(l)
(l)
Yei = {j ∈ [Y ] : [V2 ]j,i > 0}

(5)

(l)
Yei

then j, j ′ ∈ Yσ(l) (i) (i.e.,
and there exists a mapping σ (l) : X → X such that if j, j ′ ∈
(l)
observations that are clustered together in Ye are clustered in the original ROMDP).
i

Spectral learning. While in practice we do not have the exact moments, we can only estimates them
through samples. Let N be the length of the trajectory generated by policy π, then we can construct
N − 2 triples {yt−1 , yt , yt+1 } that can be used to construct the corresponding views ~v1,t , ~v2,t , ~v3,t
PN (l)−1
(l)
b p,q
and to estimate second mixed moments as K
= N1(l) t=1
I(at = l) ~vp,t ⊗ ~vq,t , with p, q ∈
PN −1
(l)
{1, 2, 3} and N (l) =
I(at = l). Furthermore, we require knowing |Xπ |, which is not
t
(l)
(l)
known apriori. Under Asm. 1 and 2, for any action l, the rank of K2,3 is indeed |Xπ | and thus
b (l) can be used to recover the rank. The actual way to calculate the efficient rank of K
b (l) is quite
K
2,3

2,3

(l)
b p,q
intricate and we postpone the details to App. B. From K
we can construct the symmetric views
ve1,t and ve3,t as in Eq. 2 and compute the estimate second and third

(l)
(l)
Lemma 3. Under Asm. 1 and 2, let Vb2 be the empirical estimate of V2 obtained using N samples
(l)
generated by a policy π. There exists N0 such that for any N (l) > N0 , l ∈ A, i ∈ Xπ w.p. 1 − δ
s
log(2Y 3/2 /δ)
(l)
(l)
(l)
(7)
:= BO
k[V2 ]·,i −[Vb2 ]·,i k2 ≤ C2
N (l)

where C2 is a problem-dependent constant independent from the number of observations Y .
5

While this estimate could be directly used to construct a clustering of observations, the noise in the
(l)
empirical estimates might lead to [Vb2 ]j,i > 0 for any (j, i) pair, which prevents us from generating
any meaningful clustering. On the other hand, we can use the guarantee in Lem. 3 to single-out the
(l)
(l)
entries of Vb2 that are non-zero w.h.p. We define the binary matrix Ve2 ∈ {0, 1}Y ×X as
(
(l)
(l)
1 if [Vb2 ]j,i ≥ BO
(l)
e
[V2 ]j,i =
,
0 otherwise
(l)

(l)

(l)

which relies on the fact that [Vb2 ]j,i − BO > 0 implies [V2 ]j,i > 0. At this point, for any l and
(l)
(l)
(l)
any i ∈ Xπ , we can generate the cluster Ybi = {j ∈ [Y ] : [Ve2 ]j,i > 0}, which is guaranteed
S
(l)
to aggregate observations correctly in high-probability. We denote be Ybc = Y \ i,l Ybi the set of
observations which are not clustered through this process. Then we define the auxiliary state space
Sb obtained by enumerating all the elements of non-clustered observations together with clusters
(l)
{Ybi }i,l , for which we have the following guarantee.
(l)

Corollary 1. Let Sb be the auxiliary states composed of clusters {Ybi } and singletons in Y c ob(l)
tained by clustering observations according to Ve2 , then for any pair of observations j, j ′ clustered
b there exists a hidden state i such that j, j ′ ∈ Yi . Finally, Sb → S as N tends to infinity.
together in S,

4 Spectral Learning UCRL

We now describe the spectral learning UCRL (SL-UC) (Alg. 2) obtained by integrating the spectral
method above with the UCRL strategy. The learning process is split into epochs of increasing
length. At the beginning of epoch k, we use the trajectory (s1 , a1 , .., sN (k−1) ) generated at previous
epoch using auxiliary states s ∈ Sb(k) to construct the auxiliary state space Sb using Alg. 12 . As
discussed in the previous section, the limited number of samples and the specific policy executed
at epoch k − 1 may prevent from clustering many observations together, which means that despite
Sb being a correct clustering (see Cor. 1), its size may still be large. While clusterings obtained at
different epochs cannot be “aligned” because of different labelling, we can still effectively merge
together any two clusterings Sb and Sb′ generated by two different policies π and π ′ . We illustrate this
procedure through Fig. 2(left). Observations y3 , y4 , and y5 are clustered together in the auxiliary
space generated by π, while y5 and y6 are clustered together using π ′ . While the labelling of the
auxiliary states is arbitrary, observations preserve their labels across epochs and thus we can safely
conclude that observations y3 , y4 , y5 , and y6 belong to the same hidden state. Similarly, we can
construct a new cluster with y9 , y10 , and y11 , which, in this case, returns the exact hidden space X .
Following this procedure we generate Sb(k) as the clustering obtain by merging Sb and Sb(k−1) (where
Sb1 = Y).

At this point we can directly estimate the reward and transition model of the auxiliary MDP constructed on Sb(k) by using standard empirical estimators. Let N (k) (y, a, y ′ ) be the number of times
a transition from observation y to y ′ through action a has
PbeenPobserved up to the beginning of
epoch k. Then we can easily construct N (k) (s, a, s′ ) = y∈s y′ ∈s′ N (k) (y, a, y ′ ), where with
an abuse of notation we write y ∈ s to denote the fact that observation y has been clustered into
an auxiliary state s at epoch k. Similarly we can compute the number of visits to any auxiliary
state-action pair N (k) (s, a) and the reward cumulated over time R(k) (s, a). Then we return the
estimates3 rb(k) (s, a) = R(k) (s, a)/N (k) (s, a) , pb(k) (s′ |s, a) = N (k) (s, a, s′ )/N (k) (s, a). The
corresponding confidence intervals are such that for any s ∈ Sb(k) and a ∈ A
2
Since Alg. 1 receives as input a sequence of auxiliary states rather than observations as in Sect. 3 the
spectral decomposition runs on a space of size |Sb(k−1) | instead of Y , thus reducing the computation complexity.
3
Since the clustering Sb(k) is monotonic (i.e., observations clustered at epoch k stay clustered at any other
epoch k′ > k), rb(k) and pb(k) can be computed incrementally without storing the statistics N (k) (y, a, y ′ ),
N (k) (y, a), and R(k) (y, a) at observation level, thus significantly reducing the space complexity of the algorithm.

6

(k)

kp(·|s, a)–b
p

(·|s, a)k1 ≤ dp (s, a) =

s

s

7S (k) log( 2ANδ
N (k) (s, a)
(k)

(k)

)

,

(k)

)
7 log( 2S AN
δ
,
(k)
2N (s, a)
hold w.p. 1 − δ, where p(·|s, a) and r̄ are the transition probabilities and reward of the auxiliary
MDP MSb(k) . At this point we can simply apply the same steps as in standard UCRL, where an
f(k) is constructed using the confidence intervals above and extended
optimistic auxiliary MDP M
value iteration (EVI) [13]. The resulting optimal optimistic policy π
e(k) is then executed until the
number samples at least for one pair of auxiliary state and action is doubled. EVI has a per-iteration
complexity which scales as O((Sb(k) )2 A) thus gradually reducing the complexity of UCRL on the
observation space (i.e., O((Y )2 A)) as soon as observations are clustered together.
|r̄(s, a) − rb(k) (s, a)| ≤ dr (s, a) =

Theorem 1. Consider a ROMDP M = hX , Y, A, R, fT , fO i with diameter DX . If SL-UC is run
over N time steps, under Asm. 1 and 2, with probability 1 − δ it suffers the total regret of
r
K 
 N (k)  X ν (k) (s, a) 
X
p
RegN ≤
DSb(k) Sb(k) log
,
(8)
(k) (s, a)
δ
N
(k)
k=1
b
s∈S

where (S

(k)

,a

) is the sequence of auxiliary state spaces generated over K epochs.

Remark. This bound shows that the per-step regret decreases over epochs. First we notice that only
the regret over the first few (and short) epochs actually depends on the number of observations Y
and the diameter DY . As soon as a few observations start being clustered into auxiliary states, the
regret depends on the number of auxiliary states Sb(k) and the diameter DS (k) . Since Sb(k) decreases
every time an observation is added to a cluster and DS (k) is monotonically decreasing with of Sb(k) ,
the per-step regret significantly decreases with epochs.4 Cor. 1 indeed guarantees that the number of
auxiliary states in Sb reduces down to |S| (XA in the worst case) as epochs get longer. Furthermore
we recall that even if the clustering Sb returned by the spectral method is not minimal, merging
clusters across epochs may rapidly result in very compact representations even after a few epochs.

Minimal clustering. While Thm. 1 shows that the performance of SL-UC improves over epochs,
it does not relate it to the (ideal) performance that could be achieved when the hidden space had
been known. In order to provid a minimal clustrting, we integrate Alg. 2 with a clustering technique similar to the one used in [9] and [21]. At any epoch k, we proceed by merging together
all the auxiliary states in Sb(k) whose reward and transition confidence intervals overlap (i.e., s and
s′ are merged if the confidence interval [b
r (s, a) ± dr (s, a)] overlaps with [b
r (s′ , a) ± dr (s′ , a)] and
[b
p(·|s, a) ± dp (s, a)]5 overlaps with [b
p(·|s′ , a) ± dp (s′ , a)]. If the number of new clusters is equal
to X, then we claim we learned the true clustering, if it is less than X we ignore this temporary
clustering and proceed to the next epoch. It worth to note that this procedure requires the knowledge
of X, while the spectral method, by its own, does not. While an explicit rate of clustering is very
difficult to determine (the merging process depends on the spectral method, whose result depends
on the policy, which in turn is determined according to the clustering at previous epochs), we derive
worst-case bounds on the number of steps needed to start clustering at least one observation (i.e.,
steps before avoiding the dependency on Y and DY ) and before the exact clustering is recovered.

Corollary 2. Let τM = maxx,π Eπ [τπ (x, x)] the maximum expected returning time in MDP M
(bounded due to ergodicity) and
N first =

C2 log(1/δ)
AY τM
AY τM
; N last =
C2 log(1/δ).
3
Omin maxi,j fO (y = j|x = i)2
Omin

(9)

After N first steps at least two observations are clustered and after N last steps all observations are
clustered (but not necessarily in the minimum hidden space configuration) with probability 1 − δ.
4

We refer to the per-step regret since an epoch may be longer, thus making the cumulative epoch regret
larger.
5
Deviation dp (s, a) on a Sb dimensional simplex.

7

y1

y1

y2

y2

y3

y3

y4

y4

y5

y5

×10

UCRL
DQN
SL-UC

3
2
1
0

Regret

π′

π

×10

5

100

3

200

300

400

500

600

700

800

900

100

200

300

400

500

600

700

800

900

100

200

300

400

500

600

700

800

900

2

y6

y6

y7

y7

y8

y8

y9

y9

2

y10

y10

1

y11

y11

1
0

x1 x2 x3 x4

5

3

0

×10

5

sqrt(N)

x1 x2 x3 x4

Figure 2: (left) Examples of clusterings obtained from two policies that can be effectively merged. (right)
Regret comparison for ROMDPs with X = 5, A = 4 and from top to bottom Y = 10, 20, 30.
This implies that after N last steps |Sb(k) | ≤ XA. Furthermore, let γr = minx,x′ ,a |r(x, a) − r(x′ , a)|
and γp = minx,x′ ,a kp(·|x, a) − p(·|x′ , a)k1 be the smallest gaps between rewards and transition
probabilities and let γ = max{γr , γp } the maximum between the two.
In worst case, using the additional clustering step together with SL-UC guarantees that after
o
n AY 2 τ
 AS 2 τM
M
log(1/δ),
max
log(1/δ),
N X = min
N
last
γ2
γ2

samples the hidden state X is correctly reconstructed (i.e., Sb(k) = X ), therefore
q
q
RegN ≤ 34DX X A(N − N X ) log(N/δ)I(N ≥ N X ) + min{N X , 34DY Y A(N X ) log(N/δ)}

We first notice that this analysis is constructed over a series of worst-case steps (see proof in
App. E.1). Nonetheless, it first shows that the number of observations Y does impact the regret
only over the first N first steps, after which Sb(k) is already smaller than Y. Furthermore, after at
most N last the auxiliary space has size at most XA (while the diameter may still be as large as
DY ). Finally, after N X steps Sb(k) reduces to X and the performance of SL-UC tends to the same
performance of UCRL in the hidden MDP.

5 Experiments

We validate our theoretical results by comparing the performance of SL-UC, UCRL2 (model based,
exact solution) and DQN (model free, function approximation) [20], two well known RL algorithms.
Since SL-UC is proposed specifically for infinite horizon environment, we are not able to compare
it with episodic setting, e.g., PSRL [22]. For DQN we implemented a three hidden-layers feed
forward network (with no CNN block), equipped with RMSprop and replay buffer. We tune the
hyper parameters of the network and report the best performance achieved by network of size 30 ×
30 × 30.

We consider three randomly generated ROMDPs (Dirichlet transition and Uniform reward with
different bias) with X √= 5, A = 4 and observation spaces of sizes Y = 10, 20, 30. Fig. 2(right)
reports the regret on a N scale. We see that in each instance the regret of UCRL√and DQN grows
much faster than SL-UC’s. While all regrets tend to be linear (i.e., growing as N ), we clearly
see that the performance of UCRL and DQN is negatively affected by the increasing number of
observations, while the regret of SL-UC stays almost constant, confirming that the hidden space X is
learned very rapidly. This experimental results are the first step towards more practical applications.
We report additional experiments in App. G.

6 Conclusion
We introduced SL-UC, a novel RL algorithm to learn in ROMDPs combining a spectral method for
recovering the clustering structure of the problem and UCRL to effectively trade off exploration
and exploitation. We proved theoretical guarantees showing that SL-UC progressively refines the
clustering so that its regret tends to the regret that could be achieved when the hidden structure is
known in advance (in higher order term). We showed that how the SL-UC gradually constructs
smaller MDPs, therefore, has lower cost in computing optimistic policy, encounters fewer number
of epochs, and suffers from lower computation cost. Finally, this work opens several interesting
8

directions to extend the results for variety of state aggregation topologies [17]. Furthermore, one
can aggregate the proposed method with other regret analyses, e.g. [8] and leverage the current
bounds.

7 Acknowledgement
K. Azizzadenesheli is supported in part by NSF Career Award CCF-1254106. A. Lazaric is supported in part by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science
and technologies 2015-2020, CRIStAL (Centre de Recherche en Informatique et Automatique de
Lille), and the French National Research Agency (ANR) under project ExTra-Learn n.ANR-14CE24-0010-01. A. Anandkumar is supported in part by Microsoft Faculty Fellowship, Google faculty award, Adobe grant, NSF Career Award CCF- 1254106, and AFOSR YIP FA9550-15-1-0221.

References
[1] Anandkumar, A., Ge, R., Hsu, D., Kakade, S. M., and Telgarsky, M. (2014). Tensor decompositions for learning latent variable models. The Journal of Machine Learning Research, 15(1):2773–
2832.
[2] Anandkumar, A., Hsu, D., and Kakade, S. M. (2012). A method of moments for mixture models
and hidden markov models. arXiv preprint arXiv:1203.0683.
[3] Azizzadenesheli, K., Lazaric, A., and Anandkumar, A. (2016a). Open problem: Approximate
planning of pomdps in the class of memoryless policies. arXiv preprint arXiv:1608.04996.
[4] Azizzadenesheli, K., Lazaric, A., and Anandkumar, A. (2016b). Reinforcement learning of
pomdps using spectral methods. In Proceedings of the 29th Annual Conference on Learning
Theory (COLT).
[5] Azizzadenesheli, K., Lazaric, A., and Anandkumar, A. (2017). Experimental results: Reinforcement learning of pomdps using spectral methods. arXiv preprint arXiv:1705.02553.
[6] Bertsekas, D. and Tsitsiklis, J. (1996). Neuro-Dynamic Programming. Athena Scientific.
[7] Cesa-Bianchi, N., Gentile, C., and Zappella, G. (2013). A gang of bandits. In Advances in
Neural Information Processing Systems, pages 737–745.
[8] Dann, C., Lattimore, T., and Brunskill, E. (2017). Ubev-a more practical algorithm for episodic
rl with near-optimal pac and regret guarantees. arXiv preprint arXiv:1703.07710.
[9] Gentile, C., Li, S., and Zappella, G. (2014). Online clustering of bandits. In ICML, pages
757–765.
[10] Gheshlaghi-Azar, M., Lazaric, A., and Brunskill, E. (2013). Sequential transfer in multi-armed
bandit with finite set of models. In Advances in Neural Information Processing Systems 26, pages
2220–2228.
[11] Gopalan, A., Maillard, O.-A., and Zaki, M. (2016). Low-rank bandits with latent mixtures.
arXiv preprint arXiv:1609.01508.
[12] Guo, Z. D., Doroudi, S., and Brunskill, E. (2016). A pac rl algorithm for episodic pomdps. In
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages
510–518.
[13] Jaksch, T., Ortner, R., and Auer, P. (2010). Near-optimal regret bounds for reinforcement
learning. Journal of Machine Learning Research, 11(Apr):1563–1600.
[14] Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2016).
Contextual decision processes with low bellman rank are pac-learnable. arXiv preprint
arXiv:1610.09512.
[15] Kontorovich, A., Weiss, R., et al. (2014). Uniform chernoff and dvoretzky-kiefer-wolfowitztype inequalities for markov chains and related processes. Journal of Applied Probability,
51(4):1100–1113.
[16] Krishnamurthy, A., Agarwal, A., and Langford, J. (2016). Pac reinforcement learning with
rich observations. In Advances in Neural Information Processing Systems, pages 1840–1848.
9

[17] Li, L., Walsh, T. J., and Littman, M. L. (2006). Towards a unified theory of state abstraction
for mdps. In Proceedings of the Ninth International Symposium on Artificial Intelligence and
Mathematics (ISAIM-06).
[18] Littman, M. L. (1994). Memoryless policies: Theoretical limitations and practical results. In
Proceedings of the Third International Conference on Simulation of Adaptive Behavior : From
Animals to Animats 3: From Animals to Animats 3, SAB94, pages 238–245, Cambridge, MA,
USA. MIT Press.
[19] Maillard, O.-A. and Mannor, S. (2014). Latent bandits. In Proceedings of the Thirty-First
International Conference on Machine Learning (ICML’14).
[20] Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller,
M. (2013). Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602.
[21] Ortner, R. (2013). Adaptive aggregation for reinforcement learning in average reward markov
decision processes. Annals of Operations Research, 208(1):321–336.
[22] Osband, I., Russo, D., and Van Roy, B. (2013). (more) efficient reinforcement learning via
posterior sampling. In Advances in Neural Information Processing Systems, pages 3003–3011.
[23] Sutton, R. S. and Barto, A. G. (1998). Introduction to reinforcement learning. MIT Press.

10

A

Proof of Lemma 3
(l)

At the end of each epoch, e.g. k, we estimate the factor matrix V2 (for all l ∈ [A]) using all
the samples collected during that epoch according to policy π
e(k) . In order to simplify the notation,
in the following we remove the dependency on k, even if all the quantities should be intended as
specifically computed at the beginning of epoch k.
In order to bound the empirical error of the moment estimators, we need to consider the properties of
the Markov chain generated by policy π
e and the fact that a single continuous trajectory is observed.
In particular, we have to carefully consider the mixing time of the underlying Markov chain (the
amount of time it takes that the underlying Markov chain converges to its stationary distribution)
and exploit the martingale property of the trajectory. This problem has been previously studied
by Azizzadenesheli et al. [4] for the general case of partially observable MDPs. Since ROMDPs are
a special case of POMDPs, we can directly rely on the following general concentration inequality.
For any ergodic Markov chain with stationary distribution ωπe , let f1→t (xt |x1 ) by the distribution
over states reached by a policy π
e after t steps starting from an initial state x1 . The inverse mixing
time ρmix,π (t) of the chain is defined as
ρmix,eπ (t) = sup kf1→t (·|x1 ) − ωπe kTV ,
x1

where k · kTV is the total-variation metric. Kontorovich et al. [15] show that for any ergodic Markov
chain the mixing time can be bounded as
ρmix,eπ (t) ≤ G(e
π )θt−1 (e
π ),

where 1 ≤ G(e
π ) < ∞ is the geometric ergodicity and 0 ≤ θ(e
π ) < 1 is the contraction coefficient
of the Markov chain generated by policy π
e.

Proposition 1 (Theorem 11 [4] POMDP concentration bound). Consider a sequence of ν observations {y1 , . . . , yν } obtained by executing a policy π
e in a POMDP starting from an arbitrary initial
hidden state. For any action l ∈ [A], ν (l) -length sequence b(l) = {(yt−1 , yt , yt+1 ); at = l}, and any
c-Lipschitz6 matrix valued function Φ(·) : b(l) → RY ×Y , we have
(l)

(l)

Φ(b ) − E[Φ(b )]

2

r
 2Y 
G(e
π) 
1
2 ν (l) log
≤
1+ √
8c
3
1 − θ(e
π)
δ
2c(ν (l) ) 2

with probability at least 1 − δ, where G(e
π ) and θ(e
π ) are, respectively, the geometric ergodicity and
the contraction coefficient of the underlying Markov chain on the hidden states (they define how fast
the underlying Markov chain converges to its stationary distribution), and the expectation is with
respect to the distribution of initial state equals to the stationary distribution.
The parameters 1 ≤ G(π (k) ) < ∞ and 0 ≤ θ(π (k) ) < 1 are well defined for Markov chain and
shows the state distribution of the Markov chain convergence to its stationary distribution (if such
distribution exists) with rate of G(π)θ(π)t . (the lower G(π) and θ(π) give the lower mixing for
corresponding Markov chain.) In this paper, we are interested in moments of our data, therefore,
Φ(·) is considered as a moment estimator.
Given the ergodicity assumption (Asm. 1) under any policy, we can apply Proposition 1 to bound
the errors for both second and third order moments. For any {p, q, r} a permutation of set {1, 2, 3}
1
r
1+ √
3
2Y
2c(ν (k) (l)) 2
(l)
(l)
b
kKp,q − Kp,q k2 ≤ G(π)
8c2 ν (k) (l)log(
)
(10)
1−θ
δ
1
r
1+ √
3
2Y 1.5
2c(ν (k) (l)) 2
(l)
(l)
c
8c2 ν (k) (l)log(
kMp,q,r − Mp,q,r k2 ≤ G(π)
)
(11)
1−θ
δ
with probability at least 1 − δ. At this point we can proceed with applying the robust tensor power
(l)
method proposed in [2] to recover V2 and obtain the guarantees of Lemma 5 of Azizzadenesheli
6

under the Hamming metric

11

et al. [4] through Proposition 4, where c =
of Lemma 3.

1
.
ν (k) (l)

We report a more detailed version of the statement

Lemma 4 (Concentration Bounds). The robust power method of Anandkumar et al. [2] applied to
c(l) returns the X (l) columns of matrix V (l) with the following confidence bounds
tensor M
3
2
r
log(2Y 3/2 /δ)
(l)
(l)
(l)
(l)
l
[V2 ](·|i) − [Vb2 ](·|i) ≤ ǫ3 = CO
:= BO
(12)
2
ν (l)
if
2


ν (l) ≥ N := max 
π

Θ(l)

4

(l)

ωπemin

2
{σmin

min

m∈{1,2,3}



 16(X (l) ) 13
:= max
, 4,
2
(l)
1

C2ω
 C 3 (ω (l) ) 3
1

1

π
emin

min

(Y 1.5 ) (l)

log(2
)Θ

(l)
δ
(Vm )}




√
2 2X (l)

min

2 (V (l) )} 
{σmin

m

m∈{1,2,3}

(13)

,

(14)
(l)

with probability at least 1 − δ, where C1 is a problem-independent constants and ωπemin :=
mini∈X (l) Pπe (x = i|a = l) where the minimization is over non-zero probabilities. In addition,
the σmin (·) operator returns the smallest non-zero singular value of its input matrix. The values of
(l)
the error BO under policy π
e is defined (see Eq.29 of Azizzadenesheli et al. [4])
s
√
)
log(2 (2Y
4
2
+
2
8e
ǫ(l)
(l)
δ )
,
(15)
BO := G(e
π ) (l) 1
+
(l)
ν (l)
) 2 (1 − θ(e
(ω
ω
π ))
π
emin

where
e
ǫ(l) ≤

√
√
2 2+1
2 2G(e
π ) 1−θ(e
π)
(l)

1

((ωπemin ) 2

r

π
emin

3
2

log( 2(Yδ ) )
ν (l)
(l)
min {σmin (Vm )})3
m∈{1,2,3}

+

min




√
2 2+1
64G(e
π ) 1−θ(e
π)
(l)

(l)

2 (V
1.5
{σmin
m )}(ωπ
emin )

m∈{1,2,3}

v


u
u log 2 Y 32
t
δ
ν (l)

,

(l)

We notice that the columns of V2 are all orthogonal (but not orthonormal) since the clusters are
non-overlapping and an observation j that can be obtained from a state i cannot be generated by
(l)
(l)
any other state i′ (i.e., for any i 6= i′ , [V2 ]T
:,i [V2 ]:,i′ = 0). As a result, Eq. 3 can be seen as
(l)

(l)

(l)

an eigendecomposition of M2 , where the columns [V2 ]:,i are the eigenvectors and ωπ (i) are
(l)
(l)
the eigenvalues. More formally, let M2 = U ΣU T be the eigendecomposition of M2 , if all
(l)
eigenvalues are distinct, the eigenvectors in U can be used to recover V2 up to a mapping function
(l)
and multiplicative factors. Nonetheless, in general V2 may have eigenvalues with multiplicity
(l)
and the eigendecomposition of M2 may return a wrong clustering since observations generated by
distinct states (and thus with different rewards and dynamics) may be aggregated together. In this
case, we have to move to the third order statistics to disambiguate between observations and cluster
them properly.

B Rank recovery
(l)

Lemma 4 holds when the rank of matrix V2 is known in advance. While this is not the case in
(l)
(l)
practice, here we show how one can estimate the rank r = Xπ(k) of V2 . Given the expansiveness
(l)

of latent MDP (Asm. 2), we have that for any policy π and any action l, Xπ
(l)

(l)

(l)

(l)

≤ X π . The rank

of the second moment matrix K2,3 is then min{ Xπ(k) , X π(k) } = r, which also corresponds to
(l)

the number of non-zero columns in matrix V2 . We can then try to estimate r through the estimate
b (l) , which according to Eq. 10, estimates K (l) up to an additive error ǫ(l) that
second moment K
2,3
2,3
2,3
12

q
decreases as O( ν 1(l) ). This means that the highest perturbation over its singular values is also at
q
1
most O( ν (l)
). We introduce a threshold function g ǫ (ν (l) ) that satisfies the condition
(l)

ǫ2,3 ≤ g ǫ (ν (l) ) ≤ 0.5σr ,

(16)

(l)
b (l) and
where σr is the smallest non-zero singular value of K2,3 . We then perform a SVD of K
2,3
discard all singular values with value below the threshold g ǫ (ν (l) ). Therefore, with probability
at least 1 − δ, the number of remaining singular values is equal to the true rank r. We are left
with finding a suitable definition for the threshold function g ǫ . From the condition on Eq. 16, we
notice that we need g ǫ to be smaller
q than a fixed value (RHS) and, at the same time, greater than a
decreasing function of order O( ν 1(l) ) (LHS). Then it is natural to define

g ǫ (ν (k) (l)) =

g
ν (k) (l)0.5−ǫ

(l)

for a suitable g > 0 and with 0 < ǫ < 0.5. Therefore there is a number N0 such that for all
(l)
ν (l) ≥ N0 the condition on Eq. 16 is satisfied and Lemma 4 holds. Therefore we restate the
sample complexity in Lemma 4 by adding the extra term to
N ← N + N0 (l).
Let N max denotes the maximum of this threshold for any action and policy.

C

Proof of Lemma 1
(l)

(l)

Under policy π, Fig. 1-right shows the structure of V2 . Given action l, the matrix V2 contains
(l)
Xπ columns and each column corresponds to a column in emission matrix (up to permutation).
(l)
We showed that the knowledge about a column of V2 reveals part of the corresponding column in
emission matrix, the entries with non-zero π(y|l). The policy, in general, partitions the observation
space to at most A partitions, Yl ∀l ∈ A and maps each partition to an action. It means that when we
condition on an action, e.g., l, we restrict ourselves to the part of observation space Yl and the input
to the spectral learning algorithm is set Yl . Therefore, the algorithm is able to partition this set to
(l)
(l)
Xπ partition. Because of the unknown permutation over columns of V2 for different actions, we
are not able to combine the resulting clustering give different actions. If we enumerate over actions,
(l)
we end up with A partition Yl and then we partition each set Yl to at most X(upper bound on Xπ ),
as a consequence, we might end up with at most XA disjoint clusters.

D

Proof of Lemma 2
(l)

We first study the eigendecomposition of M2 when its eigenvalues have multiplicity 1.
Lemma 5. For any action l ∈ [A], let the second moment in Eq. 3 have the eigendecomposition
(l)
(l)
M2 = U ΣU T . If all eigenvalues of M2 have multiplicity 1, there exists a mapping σ (l) : X → X
(l)
(l)
(l)
and multiplicative constants {Ci }i∈[X] , such that for any i ∈ Xπ and j ∈ [Y ], [V2 ]j,σ(l) (i) =
(l)
(l)
(l)
C [U ]j,i . As a result, for any hidden state i ∈ Xπ we define the cluster Ye as
i

i

(l)
Yei

(l)

= {j ∈ [Y ] : [U ]j,i > 0}
(l)

(17)

and we have that if j, j ′ ∈ Yei then j, j ′ ∈ Yσ(i) (i.e., observations that are clustered together in
(l)
Ye are clustered in the original ROMDP).
i

(l)

In Eq. 3 we show that matrix M2 is a symmetric matrix and has the following representation;
X
(l)
(l)
(l)
M2 :=
ωπ(l) (i)[V2 ]:,i ⊗ [V2 ]:,i .
(l)

i∈Xπ

13

(l)

(l)

(l)

As long as V2 ]:,i for i ∈ Xπ are orthogonal vectors, this matrix has rank of Xπ with the following
eigendecomposition;
(l)

M2 = U ΣU T
(l)

where the matrix U , up to permutation, is the orthonormal version of V2 , and Σ is a diagonal
(l)
(l)
matrix of rank Xπ with diagonal entries equal to ωπ multiplied by the normalization factors. As
(l)
a result we can use the decomposition to directly recover the non zero elements of V2 and the
corresponding partial clustering.
Let’s consider the i’th and j’th nonzero diagonal entries of matrix Σ, σi and σj , with eigenvectors
(l)
(l)
of Ui , Uj , i.e., M2 Ui = σi Ui , M2 Uj = σj Uj . In the case of no eigengap, i.e., σi = σj , for any
(l)
0 ≤ λ ≤ 1 we have M2 (λUi +(1−λ)Uj ) = σi (λUi +(1−λ)Uj ) = σj (λUi +(1−λ)Uj ). Therefore,
any direction in the span of span(Ui , Uj ) is an eigenvector and the matrix decomposition is not
(l)
unique, and we can not learn the true V2 . We relax this issue by deploying tensor decomposition
of higher order moments.
The proof of Lemma 2 directly follows from the properties of tensor decomposition in [1] and the
(l)
use of V2 to generate a partial clustering.

E Proof of Theorem 1
The overall proof is mostly based on the original UCRL proof in [13]. In the following we refer to
the exact steps in the original proof whenever we borrow results directly from it. The regret can be
decomposed as follows;
∗

RegN = N η −

N
X
t=1

rt =

K tk+1
X
X−1
k=1 t=tk

|

N
 X

η ∗ − r(xt , at ) +
r(xt , at ) − rt ,

{z

∆k

}

t=1

where K is the total (random) number of episodes, xt is the hidden state of the MDP at time t, same
as rt is the reward at time t, and r(xt , at ) is the true mean
p of reward. Using Heffting inequallity, as
in Eq. 8 in [13], the last term can be bounded as O( N log(1/δ) with high probability. We then
focus on the per-step regret ∆k . At any epoch k, from Corollary 1 we know that any auxiliary state
s ∈ Sb(k) is a cluster of observations with same same hidden state. As a result, the reward r(xt , at )
is equivalent to r(yt , at ) (recall that all observations have the same reward as their hidden state).
Therefore;
X

ν (k) (s, a) η ∗ − r(s, a) .
∆k =
a,s∈Sb(k)

The case when confidence intervals fail is bounded as in the original analysis. We now proceed with
the same decomposition as done in [13] (Eqs.10,13,16) and obtain7
X



∆k = ν (k) Pe (k) − P (k) w(k) +
ν (k) (s, a) re(k) (s, a) − r(s, a) + ν (k) I − P (k) w(k) ,
s∈Sb(k) ,a

where ν (k) is the vector of number of samples to auxiliary states in epoch k, P (k) (resp. Pe (k) ) is
the true (resp. optimistic) transition matrix over auxiliary states of policy π (k) , w(k) is the centered
version of the bias function returned by extended value iteration and re(k) (s, a) is the optimistic
reward. The first two terms account for the errors in estimating the dynamics and rewards of the
(auxiliary) MDP and can be bounded as
q
X q

∆k ≤ DSb(k) Sb(k) log(1/δ)
N (k) (s, a) + ν (k) I − P (k) w(k) ,
s∈Sb(k) ,a

7

Here√we ignore the additive regret coming from approximate extended value iteration that accounts for an
extra O( N ) regret at the end.

14

where DSb(k) is the diameter of the auxiliary MDP at epoch k and  denotes universal numerical
constants. The remaining term can be cumulatively bounded following similar steps as in Eq.18
in [13] with the only difference that the range of w(k) changes at each epoch. Thus we have
v
uK
K
X
uX

(k)
(k)
(k)
w ≤ t
I −P
ν
D
ν (k) ,
k=1

where ν (k) =
statement

P

s,a

RegN ≤ 
E.1

k=1

Sb(k)

ν (k) (s, a) is the length of epoch k. Grouping all the terms lead to the first regret

X
K

k=1

DSb(k)

q

v
uK

X q
uX
DSb(k) ν (k) .
Sb(k) log(1/δ)
N (k) (s, a) + t
s∈Sb(k) ,a

k=1

Clustering Rate

The first regret bound still contains random quantities in terms of the auxiliary MDPs generated over
episodes. In this section we derive bounds on the number of steps needed to cluster observations.
We notice that the analysis is extremely “pessimistic” and as we take worst-case values for all the
quantities involved in the analysis.
Time to clustering. We proceed as follows. We first compute the minimum number of samples
N (y) to guarantee that an observation y is correctly clustered. We then compute the length ν(y) of
an epoch so that N (y) samples are collected. Finally, we derive how many epochs K(y) are needed
before an epoch of length ν(y) is run.
We start by defining the probability that a certain action is explored. Let π be an arbitrary policy such
that action a is taken in at least one observation y belonging to a hidden state x = xy . Whenever an
agent is in state x, there is a probability P(y|x) to observe y and thus trigger action a. We define the
probability of “observing” an action a in state x under policy π as
X
απ (l) =
(18)
P(y|x)1(π(y) = a).
y∈x

Since we assumed that l is taken in at least one observation απ (l) is always non-zero and it indeed
lower-bounded by Omin . We define αp := mink∈[K],x∈X ,a∈A απ(k) (a) as the worst proportion
across all epochs, states, and actions.

Now we need need to know how fast the set S (k) converges to set X , in other work how fast is the
clustering process. From Eq. 7 and the clustering process, we know that an observation y is clustered
in xy if the number of samples ν (k) (l) obtained from the action l executed in y within a given epoch
k is such that
s
log(1/δ)
(k)
fO (y|x(y)) ≥ 2CO (l)
.
(19)
ν k (l)
By reverting the bound and taking the worse case over actions and epochs, we obtain that a sufficient
condition is to collect at least N (y) samples, with
(k)

N (y) := max 4CO (l)
l,k

log(1/δ)
.
(fO (y|x(y)))2

We can now leverage on the ergodicity of the MDP and the probability of observation of an action αp to find the minimum number of steps with an epoch to guarantee that with high probability the condition in Eq. 19 is satisfied. We define the worst-case mean returning time as
τM = maxπ maxx E[τπ (x → x)], where τπ (x → x) is the random time to go from x back to
x through policy π. By Markov inequality, the probability that it takes more than 2τM time step to
from first visit of state x to its second visit is at most 1/2. Given the definition of αp , it is clear
that if the action l is taken in state x then, this action will be taken at state x for αp portion of
the time. If we divide the episode of length ν into ναp /2τM intervals of length 2τM /αp , we have
that within each interval we have a probability of 1/2 to observe a sample from state x and take a
particular action. Therefore, the lower bound on the average number of time that the agent takes any
15

action l (that has a non zero probability to be executed in a state x) is ναp /4τM samples. Thus from
Chernoff-Hoeffding, we obtain that the number of samples of any feasible action in the epoch with
length ν is as follows;
s
ναp
ναp log(XA/δ)
∀x ∈ X , ∀l ∈ range{e
π(·|x)}; ν(l) ≥
−
4τM
2τM
with probability at least 1 − δ. At this point, we can derive a lower bound on the length of the
episode that guarantee the desired number of samples to reveal the identity of any observation is
reached. For observation y, we solve
s
ναp log(XA/δ)
ναp
−
≥ N (y)
4τM
2τM
and we obtain the condition
s
s
√
4τM
2τM
2τM
ν≥
N (y),
log(XA/δ) +
log(XA/δ) +
αp
αp
αp
which can be simplified to
ν ≥ ν(y) :=


4τM
N (y) + log(XA/δ) .
αp

(20)

With the same argument in App. D in [4] the number of required epochs to reveal observation y is
K(y) ≤ AY log2 (ν(y)) + 1.

Time to clustering. Let yfirst = arg miny∈Y K(y) be the first observation that could be clustered8
then we define Kfirst = K(ylast ) as the number of episodes and Nfirst = 4AY ν(yfirst ) the total
number of steps needed before clustering y1 correctly. Similarly, let ylast = arg maxy∈Y and Klast =
K(ylast ) as the number of episodes and Nlast = 4AY ν(ylast ) the total number of steps needed before
clustering ylast correctly. Since all the other observations will be clustered before ylast we can say that
by epoch Klast all observations will be clustered. As discussed in Lem. 1 this does not necessarily
correspond to the hidden state X but it could be an auxiliary space S with at most AX states.

Validity of the bound in Lemma 3. We also notice that Lemma 3 requires a minimum number
of samples N0 before the concentration inequality on the estimate of V2 holds. Applying a similar
reasoning as for the time for clustering, we can derive a bound on the number of episodes Ksm and
number of samples Nsm needed before the spectral method actually works (from a theoretical point
of view). As a result, a more accurate definition of Kfirst and Klast (resp. for N ) should take the
maximum between the values derived above and Ksm .
E.2

Minimal Clustering

The spectral learning algorithm has been shown to efficiently cluster the observation set to an auxiliary state space of size X ≤ S ≤ XA. As long as different clusters are merged across epochs,
we expect S (k) to tends to X , yet there is a chance that it converges to a number of auxiliary states
S 6= X. To make sure that the algorithm eventually converges to the hidden space X , we include a
further clustering technique. We adapt the idea of Gentile et al. [9], Cesa-Bianchi et al. [7] and the
state aggregation analysis of Ortner [21] and perform an additional step of Reward and Transition
Clustering. In order to simplify the notation, in the following we remove the dependency on k, even
if all the quantities should be intended as specifically computed at the beginning of epoch k.
We first recall that given any hidden state x and any action a we have r(y, a) = r(x, a) (reward
similarity) and p(·|y, a) = p(·|x, a) for all observations y ∈ Yx (transition similarity). The same
similarity measures work for auxiliary states via replacing observations with auxiliary states in the
above definitions, i.e., given any hidden state x and any action a we have r(s, a) = r(s, a) and
p(·|s, a) = p(·|x, a) for all auxiliary states s ∈ S that belong to hidden state x.9 We also recall that
8

This should be intended as the first observation that is clustered in the worst case. In practice, depending
on the policy and the randomness in the process, other observation may actually be clustered well before y1 .
9
Notice that this holds since S is a “valid” clustering in high probability.

16

high-probability confidence intervals can be computed for any s ∈ Sb any a ∈ A as
s
14Sb log(2AN/δ)
kp(·|s, a) − pb(·|s, a)k1 ≤ d(s, a) :=
2 max{1, N (s, a)}
s
b
7 log(2SAN/δ)
|r̄(s, a) − rb(s, a)| ≤ d′ (s, a) :=
.
2 max{1, N (s, a)}

(21)

At any epoch, we proceed by merging together all the auxiliary states in Sb whose reward
and transition confidence intervals overlap (i.e., s and s′ are merged if the confidence interval
[b
r (s, a) ± dr (s, a)] overlaps with [b
r (s′ , a) ± dr (s′ , a)] and [b
p(·|s, a) ± dp (s, a)] overlaps with
′
′
e In practice, the set Se is constructed by build[b
p(·|s , a) ± dp (s , a)]) and construct a new set S.
ing a fully connected graph on s ∈ Sb where each state s as a node. The algorithm deletes the edges
between the nodes when |b
r(s, a) − rb(s′ , a)| > dr (s, a) + dr (s′ , a) or |b
p(·|s, a) − pb(·|s′ , a)|1 >
′
dp (s, a) + dp (s , a). The algorithm temporarily aggregates the connected components of the graph
and consider each disjoint component as a cluster. If the number of disjoint components is equal
to X then it returns Sb as the final hidden state X , otherwise the original auxiliary state space Sb is
preserved and the next epoch is started. Notice that if s and s′ belong to the same hidden state x
then w.h.p. their confidence reward and transition intervals in Eq. 21 overlap at any epoch. Thus in
general Se ≤ X.
b ∀a ∈ A and the
Let’s define the reward gaps as follows (similar for the transitions) ∀s, s′ ∈ S,
′
corresponding x, x
γra (s, s′ ) = γra (x, x′ ) := r̄(x, a) − r̄(x′ , a) = r̄(s, a) − r̄(s′ , a) ,

γpa (s, s′ ) = γpa (x, x′ ) := kp(·|x, a) − p(·|x′ , a)k1 = kp(·|s, a) − p(·|s′ , a)k1 .

e b , where ∆
e b is (Sb − 1) dimensional simplex. To delete an edge
where p(·|x, a), p(·|s, a) ∈ ∆
S−1
S−1
′
between two states s, s belonging to two different hidden states, one of the followings needs to be
satisfied for at least for one action
s
s
b
b
7
log(2
SAN/δ)
7 log(2SAN/δ)
|b
r (s, a) − rb(s′ , a)| > dr (s, a) + dr (s′ , a) ⇒ γra (s, s′ ) >
+
2 max{1, N (s, a)}
2 max{1, N (s′ , a)}
(22)
|b
p(·|s, a) − pb(·|s′ , a)|1 > dp (s, a) + dp (s′ , a) ⇒ γpa (s, s′ ) >

s

14Sb log(2AN/δ)
+
2 max{1, N (s, a)}

s

14Sb log(2AN/δ)
2 max{1, N (s′ , a)}
(23)

For simplicity, we proceed the analysis with respect to reward, the same analysis holds for transition
probabilities. The Eq. 23 can be rewritten as follows;
!−1 s
b 2 N/δ)
28 log(2SA
1
1
p
+p
≥
2γra (s, s′ )2
max{1, N (s, a)}
max{1, N (s′ , a)}

which hold when

min{N (s, a), N (s′ , a)} >

b
56 log(2SAN/δ)
.
γra (s, s′ )2

(24)

This implies that after enough visits to the auxiliary states s and s′ , the two states would be split if
they belong to different hidden states. We notice that as S becomes smaller, more and more samples
from raw observations are clustered into the auxiliary states, thus making N (s, a) larger and larger.
Furthermore, we can expect that the transition gaps may become bigger and bigger as observations
are clustered together.
The way that spectral method clusters the observation is effected by separability of observations’
probability. But the clustering due to reward analysis (or transition or both) is influenced by the
separability in reward function (or transition function or both) and depends on gaps. These two

17

methods look at the clustering problem from different point of view, as a consequence, their combination speeds up the clustering task.
For simplicity we just again look at the reward function, same analysis applies to transition function
as well.
Regret due to slowness of Reward Clustering (Transition Clustering) Let Nar (s, s′ ) denote the
required number of sample for each of s and s′ to disjoint them.
Nar (s, s′ ) :=

b
56 log(2SAN/δ)
γa (s, s′ )2

While the underlying Markov chain is ergodic, with high probability we can say at time step N (s, s′ ),
at least for one action min{N (s, a), N (s′ , a)} ≤ N a (s, s′ ) where
4τM
Nr (s, s′ ) = min{
(Nar (s, s′ ) + log(Y A/δ))}
a
αp
In the worse case analysis we might need to have Nr = maxs,s′ Nr (s, s′ ) samples, which corresponds to at most AY log(Nr ) episode. At this time, the reward clustering procedure can output the
exact mapping. This bound can be enhance even further by considering the reward function together
with the transition process. With the same procedure we can define Np = maxs,s′ Np (s, s′ ) where
Np (s, s′ ) = min{
a

4τM
(Nap (s, s′ ) + log(Y A/δ))}
αp

(25)

with
Nap (s, s′ ) :=

b
112Sb log(2SAN/δ)
γa (s, s′ )2

Again, in the worse case analysis we might need to have Np = maxs,s′ Np (s, s′ ) samples, which
corresponds to at most AY log(Nr ) episode. Therefore the number of required episode for the agent
to declare the true mapping w.h.p., is AY log(min{Nr , Np }).

F Extended Discussion
Conjecture 1. We can extend this results to deterministic MDP. In this case we can first uniformly
explore the latent space and collect sufficient number of sample to find the exact clustering and
reduce the large MDP to the latent MDP and then apply UCRL on the latent √
MDP. Which can suffer
e X X AN ) due to UCRL in
a constant regret of pure exploration at the beginning and regret of O(D
the second phase. One of the main open questions is whether the spectral clustering method could
still provide “useful” clusterings when the state space is not fully visited (i.e., in case of non-ergodic
MDP), so that observations are properly clustered where it is actually needed to learn the optimal
policy. We can provide a partial answer in the case of deterministic ROMDPs. In fact, despite
not being ergodic, in this case we can first uniformly explore the latent space and collect sufficient
number of sample to find the exact clustering and reduce the large MDP to the latent MDP and then
apply UCRL on the latent MDP. These two-phase algorithm
would suffer a constant regret of pure
√
e X X AN ) due to UCRL in the second phase.
exploration at the beginning and regret of O(D

In RL problems, the principle of Optimism-in-Face-of-Uncertainty contributes in designing a policy
that locally improves the model uncertainty and average reward which has been shown to be an
optimal strategy. It is an open question to analyze and modify this principle for the models with
clustering where global improvement of the information in model uncertainty is required. While the
SL-UC for deterministic models reaches order optimal regret, it is not still clear how to modify the
exploration to enhance the constant regret of the pure exploration phase.

Compared to POMDP. We can compare this result with the regret bound of Azizzadenesheli et al.
[4] for POMDPs, which are a more general class than ROMDPs. Recalling that POMDPs are characterized by a diameter Dpomdp := maxx,x′ ,a,a′ minπ∈P E[τ ((x, a) → (x′ , a′ ))], the regret derived
√
e pomdp X 3/2 AY N ). The regret suffers from additional
by Azizzadenesheli
et
al.
[4]
scales
as
O(D
√
term Y because the RL algorithm in POMDP put much effort on accurate estimation of entries
of O matrix and does not exploit its specific structure. Moreover, there is an additional factor X
18

×10 5
UCRL
DQN
SL-UC

3
2
1

Reward

0

×10

3

5

100

200

300

400

500

600

700

800

900

100

200

300

400

500

600

700

800

900

100

200

300

400

500

600

700

800

900

2
1
0
3

×10

5

2
1
0

sqrt(Time)

√
Figure 3: (left)The regret comparison, A = 4, from top to bottom, Y = 10, 20, 30. The scale is T .
(right) Learning rate of SL-UC compared to UCRL and DQN. After first few rounds, it learns the
the true mapping matrix. The numbers in the bulbs are the cardinality of Aux-MDP.
in regret bound due to learning of transition tensor through spectral methods. Their experimental
results are provided here [5].

G Additional Experiments
While the results reported in the main text are obtained on actual ROMDPs, here we test SL-UC on
random MDPs with no explicit hidden space. The objective is to verify whether SL-UC can be used
to identify (approximate) clusters. Since SL-UC in high probability only clusters observations that
actually belong to the same hidden state, in this case SL-UC would reduce to run simple UCRL, as
there is no two observations that can be exactly clustered. In order to encourage clustering, we half
the (exact) confidence intervals in the attempt of trading off a small bias with a significant reduction
in the variance. We compare the regret on three random MDPs with increasing number of states. As
it is shown in Fig. 3, SL-UC is effective even in this scenario compared to UCRL and DQN. In fact,
we see from Fig. 3-right that SL-UC is able to find clusters without compromising the overall regret.
While the number of states now directly affects the performance of SL-UC, we see that it is more
robust than the other algorithms and its regret is not severely affected by an increasing number of
observations.

19

