Waiting for Evidence Before Inventing a Regime: Delay-Aware State Discovery for Latent Bandits

Many decision systems act in a world whose hidden "mode" changes over time and whose feedback arrives late. An ad platform faces shifting user regimes, and a conversion can land minutes or weeks after the click. A mining rover crosses geological zones, and assay results come back from a lab. Two literatures each handle half of this. One studies latent-state models, which infer a hidden regime from data; some of these grow the number of regimes as data demands instead of fixing it in advance. The other studies delayed feedback and has learned to measure delay by its quantiles, that is, "how long until 90% of outcomes have arrived," rather than by its mean, which can be infinite when delays are heavy-tailed. This proposal starts from a failure that appears only when the two meet. When rewards are delayed, a model that discovers regimes online mistakes missing feedback for a real change in the world. A burst of recent actions whose conversions have not arrived yet looks exactly like a new low-reward regime, so the model invents a "ghost" state and the controller acts on it.

We propose a latent-state contextual bandit that fixes this in two ways. First, every pending reward enters the regime likelihood as a censored observation: "not yet converted after age $a$" is explained partly by the delay distribution, not only by the regime. Second, the model commits to a new regime only after a delay-quantile-calibrated amount of feedback has actually arrived. This second rule replaces two separate lags in current practice with one: the hand-tuned batch size that robust online models use to suppress spurious states, and the quantile wait that delay-robust bandits use. The outcome is a controller whose number of states is learned, whose regret depends on delay quantiles rather than mean delay, and which does not hallucinate regimes when feedback is slow.

Core Claim

Our main claim is empirical and theoretical. In latent-regime bandits with heavy-tailed, censored reward delays, most spurious state creation, and much of the resulting regret, comes from treating pending rewards as information about the regime. Correcting this requires two things. The regime likelihood must be conditioned on the delay survival function. The regime-commit decision must be gated on arrived evidence, with a threshold set by a delay quantile. A fixed batch size alone does not do the job. If the claim is right, the correction will cut ghost states sharply at little cost in detection lag for real regime changes. It will also help regardless of whether the state count is learned nonparametrically or fixed at a generous upper bound.

That last clause matters. We do not claim that nonparametric priors are the key ingredient. Our key ingredient is how state inference treats missing feedback. Whether an infinite prior helps beyond a large fixed truncation is an ablation, not an assumption.

Relation to Prior Work

Our closest starting point is Linearizing contextual bandits with latent state dynamics. That paper shows that when an HMM drives contexts and rewards, the expected reward is linear in the posterior belief over hidden states. It builds Thompson-sampling and UCB controllers (L²TS, L²UCB) on beliefs tracked by online expectation-maximization. It supplies our decision layer. However, it assumes two things our setting breaks: rewards arrive instantly, and the number of states $K$ is known. The authors themselves name learning $K$ as future work.

On the state-discovery side, The Infinite Hidden Markov Model lets a hierarchical Dirichlet-process prior decide how many states are active. Doubly Outlier-Robust Online Infinite Hidden Markov Model (BR-iHMM) is our main motivating evidence. It shows that online versions of such models create spurious states when data is anomalous and suppresses this by batching state decisions over a fixed window $B$. It also documents the price: real regime changes are detected late. BR-iHMM has no actions or rewards, and its data arrives in order. Our proposal carries its batching idea into a decision loop where the "anomaly" is systematic missingness caused by delay, and it replaces the heuristic $B$ with a quantity derived from the delay distribution. RED-HDP-HMM constrains our design. Its duration model conditions on the previous observation, which becomes unavailable under delay. So we keep durations geometric (sticky) in the main method and treat observation-dependent durations as an extension.

On the delay side, several papers supply method. Linear bandits with Stochastic Delayed Feedback censors rewards arriving after a window $m$ and adds an exploration bonus for pending feedback (OTFLinUCB). It shows that too small an $m$ traps learning in linear regret on Criteo delays. Delay-Adaptive Learning in Generalized Linear Contextual Bandits widens confidence sets by missing-reward counts. A Reduction-based Framework for Sequential Decision Making with Delayed Feedback converts batched algorithms into delay-robust ones via a wait strategy whose cost is bounded by the delay quantile. Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions and Lipschitz Bandits with Stochastic Delayed Feedback show that regret can depend on quantiles alone, even when the mean delay is unbounded. All of these assume the context or state is observed and exogenous; none updates a belief over hidden transitions. Reinforcement Learning from Delayed Observations via World Models does handle partial observability under delay, but only with fixed deterministic delays and a fixed-dimensional neural latent. That is a different regime from ours.

Research Program

Setting. The environment has a hidden regime $s_t$ that evolves as a sticky Markov chain with an unknown number of states. Contexts $x_t$ are observed immediately and depend on $s_t$. The reward $r_t$, often binary like a conversion, is generated by $s_t$ and the action, but is revealed only after a random delay $D_t$ with distribution $F_D$. The delay may be heavy-tailed, and some rewards are never revealed.

The censored belief update. Contexts update the belief at once. Rewards update it retroactively when they arrive, via fixed-lag forward-backward recomputation over a window of length $Q(\tau)$, the $\tau$-quantile of delay. Before $t - Q(\tau)$, the belief is effectively settled. For an action taken at time $u$ whose reward is still pending at age $a = t-u$, the likelihood under regime $k$ with success probability $\theta_k(x_u, \text{action})$ is

$$ \Pr(\text{no reward yet} \mid s_u = k) = 1 - \theta_k(x_u,\text{action})\,F_D(a). $$

This term is close to 1 for young pending actions and approaches the ordinary non-conversion likelihood $1-\theta_k$ as $F_D(a)\to 1$. It is exactly the quantity that the delay-agnostic update gets wrong. We estimate $F_D$ online from arrived delays using a Kaplan–Meier-style estimator, which accounts for rewards still pending. We place a weak-limit sticky HDP prior over states and use a particle filter to track beliefs.

The quantile commit rule. A candidate new state is spawned tentatively, but the controller acts on the belief only after merging tentative states back into existing ones. A tentative state is promoted when the arrived rewards attributed to it reach a count $n^\star$ and its evidence against every existing state exceeds a threshold. In steady play, only a fraction $\tau$ of rewards from the candidate segment have arrived by lag $Q(\tau)$. Real regimes are therefore committed after roughly

$$ \text{lag} \approx Q(\tau) + n^\star/\tau $$

rounds. The form comes from waiting $Q(\tau)$ for a $\tau$ fraction of feedback to arrive, then accumulating $n^\star$ arrivals at rate $\tau$ per round. Under a naive design, the batch lag $B$ and the delay wait instead stack sequentially, and the batch fills with pending rather than arrived feedback.

Theory. We aim for two results. The first bounds the probability of committing a ghost state per round, in terms of $n^\star$ and the estimation error of $F_D$. It uses a likelihood-ratio concentration argument over arrived rewards only. The second bounds regret by the delay-free L²TS rate plus a per-regime-change term of order $Q(\tau) + n^\star/\tau$, with no dependence on $\mathbb{E}[D]$. We will also check whether an $\Omega(Q(\tau))$-type adaptation cost per change is unavoidable. If it is, the per-change term above would be tight up to the $n^\star/\tau$ term. If the full POMDP-style bound resists proof, we will state the bandit-level result and present the rest empirically.

Baselines

The naive reference point is L²TS from Linearizing contextual bandits with latent state dynamics, run with the true $K$ given as an oracle. It treats pending rewards as non-conversions, the natural thing a practitioner would do. It shows the size of the censoring bias with the cardinality problem removed.

The strongest existing competitor is a composition of methods from the file. It is the reduction of A Reduction-based Framework for Sequential Decision Making with Delayed Feedback, wrapped around a batched variant of L²TS with $K$ chosen by BIC sweep on a warm-up prefix. It is paired with OTFLinUCB-style censoring at window $m$ from Linear bandits with Stochastic Delayed Feedback. This is the strongest competitor because it has the only quantile-based regret guarantee available and correct delay handling for observed contexts. It lacks only delay-aware state inference and state discovery. A second strong competitor is BR-iHMM beliefs from Doubly Outlier-Robust Online Infinite Hidden Markov Model fed into the L²TS decision rule. Its batch size $B$ will be tuned on a grid.

For fairness, every method sees identical environment seeds, delay draws and context streams. Every tuned knob gets the same grid budget of 20 configurations on held-out seeds: $m$, $B$, $K$ range, $n^\star$, $\tau$. All methods run with equal particle or sample counts. On these delayed latent-bandit tasks, there is no reported result found on Lacuna for any method, including L²TS, OTFLinUCB, or the reduction. The only reported numbers relevant to state discovery are from BR-iHMM on its synthetic 100-dimensional system: RMSE 46.1 versus about 101 for a standard iHMM, and regime-detection positive predictive value 0.963 versus about 0.55, as reported in Doubly Outlier-Robust Online Infinite Hidden Markov Model. That setting has no delay.

Beating the strongest baseline means three things across delay tails: at least 20% lower cumulative regret; ghost-state rate at or below BR-iHMM's; and median detection lag for true changes no worse than the tuned BR-iHMM.

The ablations isolate the two ingredients. The first keeps the censored likelihood but uses a fixed-$B$ commit rule. The second keeps the quantile commit rule with an uncensored likelihood. The third replaces the HDP with a fixed truncation at $K_{\max}=20$, keeping both corrections.

Why not just…?

Why not just wait a fixed window $m$ and ignore anything later, as OTFLinUCB does? Censoring at $m$ removes out-of-order arrivals, but it leaves two problems. It does not tell the state model that young actions are uninformative. And Linear bandits with Stochastic Delayed Feedback shows that an $m$ below the typical delay traps learning in linear regret, while a large $m$ slows adaptation to regime changes. Our quantile commit rule is essentially this idea applied to the state-creation decision rather than the reward estimator, so the baseline and the censored-likelihood ablation directly measure what the likelihood correction adds.

Why not just fix a generous number of states and use a sticky prior? This is a real threat. A weak-limit truncation at $K_{\max}$ behaves much like a nonparametric prior in practice. It may match our method once it also gets the censored likelihood. We therefore do not stake the proposal on nonparametrics. The $K_{\max}=20$ ablation settles it. If it ties, the contribution is the delay-aware inference and commit rule, which apply to any cardinality choice. We would report it that way. Picking $K$ by BIC offline is weaker. Static sweeps cannot add a regime that first appears mid-stream, which the injected-new-regime experiment below tests directly.

Why not just use BR-iHMM's batching with a larger $B$? A larger $B$ does suppress ghosts, as its RMSE and PPV gains show. But under delay, the batch fills with pending outcomes that still bias the likelihood, and suppressing the ghosts requires $B$ to grow with the delay tail. That grows detection lag roughly additively with $Q(\tau)$ on top of $B$. The trade-off curve of ghost rate against detection lag, traced over $B$ versus over $n^\star$, is the experiment that decides this.

Proposed Experiments

The first testbed is semi-synthetic. It uses the rover-mining latent bandit of Linearizing contextual bandits with latent state dynamics, with 3 to 6 true regimes, with reward delays resampled from the empirical Criteo conversion-delay distribution used in Linear bandits with Stochastic Delayed Feedback, and with its permanently censored non-conversions retained. We will add controlled geometric and Pareto delays whose tail index ranges down to infinite mean. That lets us show regret tracking $Q(\tau)$ rather than $\mathbb{E}[D]$. In a variant, a new regime is introduced halfway through the run. This tests on-line state creation against fixed-$K$ and BIC baselines. Metrics are cumulative regret; ghost-state rate, measured as positive predictive value of committed states against ground truth; median and 90th-percentile detection lag for true changes; and active-state count over time.

The second testbed reuses BR-iHMM's streams. We take the synthetic 100-dimensional switching system with 1% outliers and the hourly electricity-demand series with its COVID-19 shift, both from Doubly Outlier-Robust Online Infinite Hidden Markov Model. Each is recast as a decision problem with delayed, heavy-tailed revelation of the target signal. On the synthetic system with delay set to zero, we first check that our inference roughly reproduces BR-iHMM's reported RMSE 46.1 and PPV 0.963 before adding delay.

The decisive check is a mechanism test on the first testbed. Hold the true regime fixed, and send a burst of actions whose rewards are delayed by a heavy tail. The delay-agnostic methods should commit a ghost state during the burst. Our method should not. As the tail grows, the gap in regret should widen in proportion to how many ghost states the baselines commit. If ghost creation turns out to be rare for the tuned baselines, or if our regret gain does not follow the ghost count, the central claim is wrong and we will report that.