Reinforcement Learning of POMDPs using Spectral Methods

1. Introduction

• POMDP learning must infer hidden state transitions and rewards from noisy observations, while planning with known parameters is PSPACE-complete.The paper identifies estimating the latent model and combining estimation, planning, and exploration–exploitation with guarantees as central challenges.Source: §1 · p. 2

1.1. Summary of Results

• The algorithm achieves order-optimal regret, with a bound described as similar to UCRL’s MDP regret and matching the MDP lower bound.The guarantee is with respect to the best memoryless policy; the POMDP diameter extends the MDP passage-time notion to memoryless observation-based policies.Source: §1.1 · pp. 2–3
• SM-UCRL runs variable-length episodes, estimates POMDP parameters spectrally, and updates its policy using an optimization oracle for memoryless policies.Optimism over confidence intervals combines exploration and exploitation; the analysis requires episodes to collect samples under a fixed policy.Source: §1.1 · pp. 2, 4
• Conditioning on actions and using memoryless policies lets the authors construct conditionally independent views for spectral estimation from fixed-policy trajectories.They estimate parameters separately for each action and derive confidence intervals; their concentration analysis also avoids requiring samples from the policy’s stationary distribution.Source: §1.1 · p. 4
• The analysis assumes more observations than states under spectral non-degeneracy conditions, a setting associated with spoken-dialogue and medical applications.The paper says the assumption can be relaxed to cover a wider family of POMDPs.Source: §1.1 · p. 4

1.2. Related Work

• Prior POMDP approaches include Bayesian RL without regret guarantees and model-free methods whose locally optimal policies can be arbitrarily suboptimal.Other approaches use policy search or random exploration; the paper positions its method as episodic POMDP learning with regret guarantees.Source: §1.2 · pp. 5–6

• The model comprises finite state, action, observation, and reward spaces, with transition, observation, and reward densities defining its dynamics and outputs.Source: §2 · p. 7
• The policy class consists of stochastic memoryless policies that assign nonzero probability to exploring every action.Source: §2 · p. 8
• An optimization oracle supplies the best policy within the memoryless policy class, rather than the generally optimal policy over the belief-MDP.Source: §2 · p. 8
• Every policy in the considered policy set induces an ergodic Markov chain with positive stationary probability for every state.Source: §2 · p. 8
• The observation matrix’s full column rank makes state observation distributions linearly independent, distinguishes states, and implies that the observation space is at least as large as the state space.Source: §2 · p. 9
• For each action, an invertible transition matrix is assumed, a sufficient condition for recovering the transition tensor.Source: §2 · p. 9

3. Learning the Parameters of the POMDP

• A trajectory collected under a policy in the specified policy set supplies data for estimating the POMDP parameters.Source: §3 · p. 9

3.1. The multi-view model

• For each action, three observable views are constructed; conditioning on the hidden state and selected action makes them independent, enabling spectral recovery of latent-state factors.Source: §3.1 · p. 10

3.2. Recovery of POMDP parameters

• The method recovers one view spectrally, obtains other views by inversion, and uses the recovered views to derive observation, reward, and transition models.Source: §3.1 · p. 11, §3.2 · pp. 11, 13
• Separate action-wise decompositions can permute hidden-state labels, so the shared observation matrix is used to align them when its columns are sufficiently separable.Source: §3.2 · p. 13
• Estimation accuracy depends on action-wise sample counts, policy exploration, and Markov-chain mixing; the parameter bounds also depend on model and view conditioning.Source: §3.2 · pp. 13–15
• With repeated trials of each action, parameter-estimation errors decrease at rate eO(1/N(l)), and the estimates converge to the true POMDP parameters.Source: §3.2 · p. 14
• The transition-model error bound is worse than the observation- and reward-model bounds by a factor of X^2.Source: §3.2 · p. 14
• Poor visitation of any state can affect estimates for other states, so accurate reconstruction requires ergodicity and coverage of the whole state space.Source: §3.2 · p. 15

The algorithm

• The spectral estimation procedure works with samples collected under any policy, so it can be integrated into strategies that change policies over time.SM-UCRL reruns the spectral method using samples associated with the policy that generated them.Source: §4 · pp. 15–16
• At each episode, SM-UCRL estimates a POMDP, builds plausible models from confidence intervals, and executes an optimistic memoryless policy until an action’s sample count doubles.The estimates reuse the largest past-episode sample set separately for each action.Source: §4 · pp. 15–17

Regret analysis

• SM-UCRL’s regret has the same N-dependence as the MDP bound, giving vanishing per-step regret and a minimax-optimal horizon dependency.The comparison concerns the dependence on N; the paper notes that the POMDP diameter can be larger because policies use observations rather than states.Source: §4 · p. 18
• The regret bound’s POMDP-specific complexity includes observation and reward dimensions, while its X^(3/2) term includes a contribution from estimating the transition tensor.The paper attributes the other X term to a factor shared with MDP bounds.Source: §4 · p. 18

Computability of confidence intervals

• Computing the confidence intervals requires parameters λ(l) that may not be available; hand-tuned replacements can increase regret constants or weaken the probability guarantee.The paper also notes that estimating λ(l) from data adds a lower-order regret term.Source: §4 · p. 19

Relaxing assumptions

• The stated regret analysis assumes a full-column-rank observation matrix, but an alternative third view can use rewards and observations jointly when they are informative enough to reconstruct hidden states.This relaxation can worsen transition-model bounds, although larger singular values may offset that in the final bound.Source: §4 · pp. 19–20

5. Conclusion

• SM-UCRL combines spectral POMDP parameter estimation with an optimistic approach to exploration–exploitation.The resulting algorithm has confidence intervals on parameters and a minimax optimal regret bound.Source: §5 · p. 21
• SM-UCRL cannot accumulate samples across episodes because the theorem requires samples from a fixed policy.The paper notes that the restriction has no very negative impact on the regret bound, while pooling samples with guarantees remains open.Source: §5 · p. 21
• Future work includes extending the approach from memoryless to bounded-memory policies and from POMDPs to predictive state representations.The paper describes PSRs as allowing representation of more sophisticated dynamical systems.Source: §5 · p. 21

6. Table of Notation

• The POMDP notation covers state, observation, action, and reward spaces, along with transition, observation, reward, and policy models.It also defines expected average reward and the best expected average reward over policies.Source: §6 · p. 22
• Estimation notation includes action-conditioned views, their covariance matrices and singular values, and second- and third-order moments.It also names estimates of the observation, reward, and transition densities and their upper confidence bounds.Source: §6 · p. 22
• Algorithm notation tracks cumulative regret, episode-level parameter estimates and plausible models, action sample counts, and the optimistic policy.The table also defines N as the minimum sample count needed to meet Theorem 3’s condition and ωmin as the smallest stationary probability over actions, states, and policies.Source: §6 · p. 22

Appendix A. Organization of the Appendix

• Appendix A places proofs of the main results in Sections B–E and technical tools from Section I after preliminary empirical results in Section F.It also summarizes additional notation used throughout the appendices.Source: Appendix A · p. 27

Appendix B. Proof of Lemma 2

• The second view relates observations and rewards to hidden states, using their independence to recover the reward model.The proof then uses the policy to normalize action probabilities when recovering the observation model.Source: Appendix B · p. 28
• The observation model is recovered from the second view for each observation and action.The proof repeats the procedure for each observation to obtain the full observation model.Source: Appendix B · pp. 28–29
• The third view gives the transition model by combining the conditional observation probability with the state-transition probability.With the known policy and observation matrix, the proof applies the observation matrix pseudoinverse to recover transitions for each state and action.Source: Appendix B · p. 29

Appendix C. Proof of Thm. 3

• The proof’s core statements assume samples come from the stationary distribution induced by policy π; Theorem 4 additionally accounts for nonstationary samples.The analysis builds on prior HMM spectral-method results.Source: Appendix C · p. 29
• Independently symmetrizing the first and second views can produce inconsistent state indices, so the proof computes other views by inverting Eq. 4.The third-view accuracy guarantee adapts a result by Song et al. (2013).Source: Appendix C · pp. 29, 31
• The second view is estimated by inverting Eq. 4 using estimated covariance matrices and the third view.The proof gives its guarantee under stated sample-size conditions with probability 1 − 3δ.Source: Appendix C · p. 32

Y R log(2Y 2+Y AR

• Theorem 3’s proof derives estimates using the second and third views, starts with a reward-bound step, and aligns action-specific observation-matrix columns despite their differing state permutations.For observation, it defines the estimate as the per-action estimate with the smallest confidence interval.Source: Appendix C · pp. 32–33, Y R log(2Y 2+Y AR · pp. 34–35

Appendix D. Proof of Theorem 4

• The proof adapts UCRL regret analysis to spectral POMDP estimates, decomposing regret into burn-in, confidence failures, and per-episode terms.The analysis explicitly separates the initial episodes before the sample condition holds from later regret terms.Source: Appendix D · pp. 36, 37, 39, 43
• The burn-in analysis bounds how many episodes are needed for every action to meet the sample condition used by Theorem 3.It studies action-specific sample collection and derives a sufficient episode count for the confidence intervals to apply.Source: Appendix D · pp. 37–38
• Confidence-interval failures are bounded separately by controlling the probability that the true POMDP falls outside the admissible model set.The proof adjusts confidence levels over time and bounds the resulting regret contribution.Source: Appendix D · p. 39
• Per-episode regret is decomposed into reward-model error and error from the transition and observation models.The proof bounds model-estimation terms using Theorem 3 and controls cumulative residual terms with a diameter bound and Azuma’s inequality.Source: Appendix D · pp. 40, 42, 43
• The final accounting combines the burn-in, confidence-failure, and per-episode bounds to obtain the theorem’s high-probability regret statement.The episode-count argument also gives K N ≤ A log2 N.Source: Appendix D · pp. 43–44

Appendix E. Proof of Remark 2 in Section 4

• The transition tensor estimate is constructed by solving linear systems using estimates of the observation and reward models and the policy.The proof frames the construction through a system like Equation 7 before deriving the transition tensor.Source: Appendix E · p. 44
• The transition-error analysis controls matrix perturbations and the pseudoinverse of the estimated matrix to bound the tensor estimation error.It uses a spectral-norm perturbation bound and a lower bound involving the matrix’s X-th singular value.Source: Appendix E · pp. 45–46
• The regret proof follows Theorem 4 except for its final aggregation step, where cumulative transition-model estimation error is included.The proof then gives a per-episode regret bound and the resulting final statement.Source: Appendix E · pp. 46–48

Appendix F. Experiments

• The parameter-estimation experiment reports that transition-tensor estimation takes longer than estimating the observation matrix and reward tensor.The transition tensor is estimated after tensor decomposition and has more parameters than the observation and reward matrices.Source: Appendix F · p. 48, Figure 3 · p. 49
• SM-UCRL converges faster and to a better policy than UCRL-MDP, Q-learning, and random-policy baselines in the synthetic comparison.The reported setting has X = 2, Y = 4, A = 2, R = 4, and rmax = 4.Source: Appendix F · pp. 48–49, Figure 3 · p. 49

Appendix G. Concentration Bound

• The appendix extends concentration results for scalar functions to matrix-valued functions of HMM samples.The bound applies to c-Lipschitz matrix-valued functions and arbitrary initial state distributions.Source: Appendix G · p. 50
• The HMM concentration bound relates deviations from a stationary-distribution expectation to the geometric ergodicity constant.It applies to finite observation sequences with arbitrary initial state distributions.Source: Appendix G · p. 50
• The POMDP concentration bound covers finite observation samples grouped by action and allows an arbitrary initial state distribution.Its stated guarantee uses the geometric ergodicity constant and an expectation under the stationary initial distribution.Source: Appendix G · pp. 50–51
• The POMDP result supplies a matrix-valued concentration guarantee for samples associated with a specified middle action.The bound’s expectation is defined for samples with that action and a stationary initial distribution.Source: Appendix G · pp. 50–51

Appendix H. Proof of Thms. 10 and 11

• The proof relies on results from Tropp (2012) and Kontorovich et al. (2008, 2014), with minor modifications.The passage introduces an inequality used in the proof.Source: Appendix H · p. 51
• The proof first bounds the deviation of Φ from its expectation under the same initial distribution used to generate Φ.The passage identifies this as the upper-confidence-bound step in Theorem 12.Source: Appendix H · p. 51
• It then bounds the difference between that expectation and the expectation under the stationary initial distribution.The sketch attributes this bound to Kontorovich et al. (2014).Source: Appendix H · p. 51

Appendix I. Concentration Bound

• Theorem 12 gives a matrix Azuma concentration bound for a Lipschitz matrix-valued function of observations from an HMM.For symmetric matrices, the dimension term reduces to d and the constant 8 reduces to 2; the result also extends to memoryless-policy POMDPs.Source: Appendix I · pp. 51–52
• Theorem 13 provides concentration bounds for multi-view samples from a memoryless-policy POMDP that share a middle action.Its proof combines matrix concentration results with the bounds for HMMs and tensor moments.Source: Appendix I · p. 52, Proof · p. 52

Proof

• The proof controls deviations under an arbitrary initial-state distribution and then relates them to expectations under the stationary distribution.The authors state that the stationary-distribution deviation is negligible compared with the other error term.Source: Proof · p. 57

Appendix J. Whitening and Symmetrization Bound

• The whitening and symmetrization bound applies to an HMM with k hidden states and three-view factor matrices, yielding whitened view components with high probability.The stated procedure uses tensor symmetrization, whitening, and a robust power method with low-order polynomial computation complexity.Source: Appendix J · p. 58

Appendix K. Whitening and Symmetrization Bound Proof

• The proof starts from second- and third-order cross-moments, symmetrizes the tensor, and whitens it into an orthogonal symmetric tensor for power iteration.The power method is used to compute the view components, with results stated up to permutation.Source: Proof of Thm. 16 · pp. 59, 60, 62, 63
• The total deviation in recovering factor-matrix columns aggregates empirical-average, symmetrizing, and whitening errors.The proof bounds these error sources to establish its recovery guarantee.Source: Proof of Thm. 16 · pp. 60–61
• De-whitening reconstructs the original view-matrix columns from the recovered whitened components.The proof notes that the same recovery process applies to the other two views.Source: Proof of Thm. 16 · p. 64