When an agent cannot see the true state of its environment, it has to guess how many hidden states exist. Recent theory shows such agents can still learn efficiently, with regret (lost reward relative to the best policy) growing only like the square root of the number of episodes. That guarantee holds when observations "reveal" the hidden state, meaning that different hidden states produce measurably different short observation sequences. Two practical obstacles remain. First, the agent must be told the number of hidden states in advance. Second, it must solve an optimistic planning problem that is computationally intractable. We propose an agent that addresses both. It starts with a single hidden state. It splits a state into two only when a finite-sample test shows that the two halves produce observation sequences the agent could actually tell apart. It replaces the intractable optimistic search with a small ensemble of ordinary model fits on randomly perturbed data, and it acts on the best of them.
The design rule comes from an unexpected place: word sense induction, the unsupervised discovery of how many meanings a word has. On realistic corpora, flexible clustering methods split monosemous words into spurious senses. They lose to the trivial rule "one cluster per word," which scores 73.6 F-B³ on SemCor-WSI, while GPT-4o scores 66.9 (In the LLM era, Word Sense Induction remains unsolved). Hidden-state discovery in reinforcement learning has the same failure mode. In the theory it is worse than a cosmetic problem, because a spurious split creates two states with nearly identical observation distributions. That drives the revealing constant toward zero, and the known regret bounds blow up as that constant shrinks.
Core Claim
A nonparametric hidden-state model is safe for provably efficient exploration only if every split it makes preserves revealingness. We make "revealing" precise using the α-weakly revealing condition of When Is Partially Observable Reinforcement Learning Not Scary?. That paper requires the multi-step emission matrix (the map from hidden state to the distribution over the next $m$ observation–action steps) to have minimum singular value at least $\alpha>0$. It shows that Optimistic Maximum Likelihood Estimation (OMLE) then achieves $O(\sqrt{K})$ regret over $K$ episodes. We conjecture the following, and aim to prove it. Suppose an agent splits a state only when the empirical minimum singular value of the enlarged model exceeds a threshold $\hat\alpha_{\min}$, inflated by a confidence width that shrinks with data. Suppose it explores through perturbed-history ensembles rather than an optimistic oracle. Then its regret is
$$R_K = \tilde O\!\left(\mathrm{poly}(d, A, O, H, 1/\hat\alpha_{\min})\sqrt{K}\right),$$
where $d$ is the number of states the agent actually instantiates, $A$ and $O$ are the action and observation counts, and $H$ is the horizon. This differs from OMLE's bound, which depends on the true $|S|$ and the true α. The square-root form is inherited from OMLE's likelihood-ratio confidence analysis. The new part is bounding the regret paid during the phases before each split. The natural target for $d$ is the rank of a predictive state representation (a description of state as predictions of future observable events). In PAC Reinforcement Learning for Predictive State Representations this rank governs sample complexity, and it can be far smaller than the number of physical states.
Relation to Prior Work
The proposal builds most directly on two lines of work.
The first bounds regret in POMDPs (partially observable Markov decision processes) and assumes a known state count and an optimistic planning oracle. This includes OMLE; OOM-UCB in Sample-Efficient Reinforcement Learning of Undercomplete POMDPs, which uses observable-operator moment estimates with confidence bonuses; and CRANE for predictive state representations. All three get statistical efficiency by maximizing value over a confidence set, which is the step that is intractable. These papers supply our analysis template, and we remove their oracle.
The second line makes optimism tractable in fully observed problems. Randomized Exploration in Reinforcement Learning with General Value Function Approximation fits $M$ least-squares regressions on Gaussian-perturbed rewards and acts greedily on their maximum. It proves $\sqrt{T}$ regret with $M=\tilde O(d)$, although $M=8$ or $16$ suffices empirically. PC-MLP moves optimism into a feature-covariance bonus so that an off-the-shelf planner can be used. Both methods require directly observed state–action features, and neither has been extended to hidden states. We supply that extension by perturbing the log-likelihood of past trajectories rather than rewards. Each ensemble member is then an ordinary approximate maximum-likelihood fit, with no constrained optimization involved.
The closest existing combination of POMDPs and nonparametrics is the infinite POMDP of The Infinite Partially Observable Markov Decision Process. It places a hierarchical Dirichlet process prior on states, infers them by beam sampling, and plans by forward tree search. It found that compact models suffice for control: 2 inferred states for a 51-state dialog task, and 7.36 on average for a 26-state gridworld. That result motivates us, because it suggests decision-relevant models are small. It also leaves exactly our gap: it has no regret bound, no guarantee that inferred states remain distinguishable, and an expensive sampler. Stick-Breaking Policy Learning in Dec-POMDPs grows controller memory with a stick-breaking prior and variational inference, which is also without regret guarantees.
From sense induction we borrow a lesson rather than a method. Stick-breaking spawn rules whose new-cluster probability is proportional to $\alpha/(n-1+\alpha)$, as in AdaGram and Infinite SCAN, split according to prior mass and fit. The SemCor-WSI result shows such rules over-split when the truth is mostly monosemous. Our split test is grounded in distinguishability instead.
Research Program
The algorithm runs in epochs. At the start of each epoch the agent holds a $d$-state model. It proposes a split of the state whose posterior-weighted observation residual is largest, fitting the two halves by a few EM steps initialized from a spectral moment estimate. It then accepts the split only if two conditions hold. The held-out log-likelihood must improve by more than a confidence width. The estimated $m$-step emission matrix of the split model must also keep its minimum singular value above $\hat\alpha_{\min}$ plus a matrix-concentration width of order $\sqrt{\log(1/\delta)/n}$, where $n$ is the number of visits to the parent state; that rate comes from standard matrix concentration of empirical emission frequencies. Within an epoch, exploration uses $M$ models. Each is fit by maximum likelihood to past trajectories, with each trajectory's log-likelihood reweighted by independent random multipliers. The agent plans in each finite small model and executes the policy whose planned value is highest.
The theory work proceeds in three steps. The first is a split-phase lemma: an unsplit state that truly hides two revealing states produces a likelihood gap growing linearly in visits, so the split is accepted after a bounded number of episodes. The second is a no-spurious-split lemma, which shows that the singular-value guard keeps the instantiated model's α bounded below with high probability. The third is a perturbed-likelihood optimism lemma, the analogue of the constant-probability-optimism argument in the perturbed-history paper, transplanted to OMLE's confidence set.
Planning inside each sampled model remains hard in general. We do not claim otherwise. The claim is that we reduce one constrained maximization over a continuous model set to $M$ unconstrained fits plus $M$ planning calls on small explicit models. For POMDPs with deterministic transitions, those calls run in polynomial time, as shown in the OOM-UCB paper. Elsewhere we use point-based planning and report its error.
A secondary study applies the same distinguishability guard to word sense induction. Here a word's contexts are clustered in BERT embedding space, and a cluster is split only when the two children are separable beyond a sample-size-dependent margin. This tests whether the guard is a general antidote to over-splitting, independent of reinforcement learning.
Baselines
The naive reference is a single-state model, which amounts to reactive control on the current observation. In the sense-induction study the counterpart is one cluster per lemma at 73.6 F-B³ on SemCor-WSI (In the LLM era, Word Sense Induction remains unsolved). Any method that cannot beat this has learned nothing about hidden structure.
The strongest statistical competitor is OMLE given the true state count. It has the best known regret rate for weakly revealing POMDPs, so it is the oracle-informed target we must approach without the oracle and without the true count. We implement its optimistic step by exhaustive search over a finite discretized confidence set on small instances only, with the same likelihood estimator and planner as ours. Beating it means matching its regret within a constant factor while using less wall-clock time per episode. Matching alone already counts, because our agent is not given the state count.
The strongest nonparametric competitor is the infinite POMDP with beam sampling and forward search. It shares our goal of discovering the state count and has reported compact models, 2 states on dialog and 7.36 on gridworld. It gets the same episodes and the same compute budget per decision. Beating it means lower cumulative regret together with fewer spurious near-duplicate states, which we measure by the minimum pairwise total-variation distance between learned emission distributions. No reported regret result was found on Lacuna for the infinite POMDP, so we must run it ourselves.
The strongest tractable-memory competitor is linear TD learning with POLITEX on truncated histories from Scalable Policy-Based RL Algorithms for POMDPs. It avoids both the oracle and the state count. We tune its history length over the same budget used to tune our $\hat\alpha_{\min}$.
Two ablations isolate our ingredients. In the first, the singular-value guard is removed so that splits use likelihood alone; this is the analogue of stick-breaking spawning. In the second, the perturbed ensemble is replaced by a single maximum-likelihood fit acted on greedily, which removes exploration. A separate sweep varies $M$ from 1 to 32.
Why not just…?
Why not just pick the state count by cross-validated likelihood or BIC, then run OMLE? This is the most serious threat, and the likelihood-only ablation is designed to settle it. Likelihood-based selection rewards any split that improves fit. Two states with nearly identical emissions can improve fit slightly while collapsing α. The sense-induction evidence shows that likelihood-driven flexibility over-splits on natural distributions. If the ablation matches the full method on regret and on learned α, the guard is unnecessary and we will report that.
Why not just over-provision states and let optimism sort it out? Over-provisioning creates an overcomplete model with tiny α. The bounds in the OMLE and OOM-UCB papers scale inversely with α, so a larger guessed count raises the sample cost rather than lowering it. We test this directly by running OMLE with 2× and 4× the true count.
Why not just use posterior sampling, which is already a tractable randomized optimism? Online Learning for Unknown Partially Observable MDPs gives $\tilde O(T^{2/3})$ regret for continuous parameters, but it assumes a known observation model, which is exactly what state discovery cannot assume. A Bayesian infinite POMDP with Thompson sampling is a fair variant, and we include it alongside the beam-sampling baseline.
Why not just use truncated-history memory? The truncation analysis needs uniform filter stability. The cited paper itself identifies T-Maze, where a single early cue decides the final action, as a case where truncation fails. We include T-Maze precisely to show this.
Proposed Experiments
The environments are Tiger and Tiger-3, including the reward shift after 100 episodes used in the infinite POMDP study; the 26-state gridworld and 51-state dialog task; T-Maze at corridor lengths 5 through 50; and combinatorial locks. The locks are the hard instances from the predictive-state-representation lower bounds, and we construct them with and without a revealing signal. We measure cumulative regret over $K$ episodes, the number of instantiated states, the learned minimum singular value, and wall-clock time per episode.
Three checks are decisive. First, on revealing locks, the slope of log-regret against log-K should be about 0.5 for our method, while the likelihood-only ablation should show either higher regret or a collapsed learned α. Second, on the 51-state dialog task, our method should instantiate a small number of states, comparable to the infinite POMDP's 2. Third, on non-revealing locks, every method, ours included, should fail, consistent with the lower bound. A method that appears to succeed there would indicate a bug.
In the sense-induction study on SemCor-WSI, the guarded splitter must exceed 73.6 F-B³ to show it escapes the one-cluster trap. Merely beating GPT-4o's 66.9 is not enough.
References
- In the LLM era, Word Sense Induction remains unsolved
- When Is Partially Observable Reinforcement Learning Not Scary?
- PAC Reinforcement Learning for Predictive State Representations
- Sample-Efficient Reinforcement Learning of Undercomplete POMDPs
- Randomized Exploration in Reinforcement Learning with General Value Function Approximation
- PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Exploration
- The Infinite Partially Observable Markov Decision Process
- Stick-Breaking Policy Learning in Dec-POMDPs
- Infinite SCAN: An Infinite Model of Diachronic Semantic Change
- Scalable Policy-Based RL Algorithms for POMDPs
- Online Learning for Unknown Partially Observable MDPs