Technical Summary: Adaptive Exploration for Latent-State Bandits

1. Problem Formulation

The paper addresses a non-stationary multi-armed bandit problem where reward distributions depend on an unobserved (latent) Markov state that evolves autonomously over time. Unlike standard contextual bandits, the learner cannot observe the state $s_t$ directly; they only observe the selected action $a_t$ and the resulting stochastic reward $r_t$.

The core challenge is that the optimal arm changes as the hidden state transitions, but the learner must infer the current state solely from the history of actions and rewards. This setting introduces three specific technical difficulties:

1. Confounded Reward Estimation: Standard algorithms average rewards over the state distribution, leading to systematic bias when the optimal arm varies across states.
2. Temporal Reward Attribution: It is difficult to distinguish whether a change in reward performance is due to learning progress or a transition in the hidden state.
3. Limited State Information: The algorithm cannot condition on state features directly and must rely on indirect signals, a task that becomes harder as the state space grows.

The goal is to minimize dynamic regret against a state-aware oracle, defined as the cumulative difference between the reward of the optimal arm for the current hidden state and the arm actually selected.

2. Methodology

The authors propose a family of algorithms that integrate Lagged Context and Probing Strategies into the LinUCB framework. The approach avoids explicit estimation of the latent Markov transition model, instead relying on low-dimensional statistics to separate states.

2.1 Lagged Context (LC-UCB)

The first component, Lagged-Context UCB (LC-UCB), treats the previous action-reward pair $(a_{t-1}, r_{t-1})$ as a contextual feature vector $\phi_t$.

• Intuition: Under slow Markovian state dynamics, the previous reward provides information about the previous state $s_{t-1}$, which is highly correlated with the current state $s_t$.
• Mechanism: The algorithm learns a mapping from $(a_{t-1}, r_{t-1})$ to the current reward $r_t$. This allows the learner to implicitly track the state and select the arm optimal for the inferred recent state, rather than the average over all states.
• Limitation: LC-UCB can fail if multiple states produce similar rewards for the same action (non-identifiability), leading to ambiguity in state inference.

2.2 Probing for State Fingerprints

To resolve ambiguity, the authors introduce probing strategies that generate "state fingerprints"—joint observations of rewards from multiple arms that uniquely identify the hidden state. Two paradigms are proposed:

1. Randomized Probing UCB (RP-UCB): Applicable when multiple experimental units (e.g., users) can be assigned different arms simultaneously. It collects true joint observations $(r_0, r_1)$ from the same time step.
2. Sequential Probing UCB (SP-UCB): Applicable for single-unit settings. It samples arms consecutively (e.g., arm 0 at $t$, arm 1 at $t+1$) and treats the pair $(r_t, r_{t+1})$ as a synthetic fingerprint. This relies on the assumption that the state is "sticky" (high self-transition probability) so that the state does not change between the two probes.

2.3 Adaptive Exploration (AdaRP-UCB / AdaSP-UCB)

Fixed-schedule probing incurs regret even when the model is confident. The authors propose Adaptive Probing variants that refresh fingerprints only when necessary, using three gating mechanisms:

• Residual Gate: Triggers a probe if the prediction error (Studentized residual) exceeds a threshold, indicating model drift or a state transition.
• Uncertainty Gate: Triggers a probe if the margin between the top two UCB scores is small, indicating high uncertainty in arm selection.
• Staleness (Hazard) Gate: Triggers a probe if the fingerprint has not been updated for a duration defined by an exponential hazard function, preventing the use of outdated information.

These gates are subject to a minimum inter-probe gap ($\tau_{min}$) to prevent oscillatory behavior.

3. Key Contributions

1. Algorithmic Framework: The development of LC-UCB, RP-UCB, SP-UCB, and their adaptive variants (AdaRP-UCB, AdaSP-UCB) that combine lagged context with coordinated probing to handle latent-state bandits without explicit Markov model estimation.
2. Theoretical Analysis: A decomposition of dynamic regret into three components: representation ambiguity (approximation error), probe cost, and drift after a fingerprint becomes stale. The paper provides bounds showing that adaptive probing minimizes regret by balancing these factors.
3. Empirical Validation: Systematic evaluation across varying numbers of hidden states ($S$), transition rates (self-transition probability $p_{stay}$), reward noise ($\sigma$), and time horizons ($T$).

4. Experimental Results

The algorithms were evaluated against classical baselines (UCB1, Thompson Sampling), adversarial methods (EXP3), and non-stationary methods (Sliding Window UCB, Discounted UCB).

• Performance: The adaptive probing methods (specifically AdaRP-UCB and AdaSP-UCB) consistently outperformed all baselines in environments where the summaries (fingerprints) could distinguish states and were updated frequently enough.
  • AdaRP-UCB achieved the lowest regret in 12 out of 13 randomized configurations, showing significant gains in volatile environments.
  • AdaSP-UCB performed best in single-unit settings with low noise, slow mixing, or large state spaces.
• Failure Modes: The paper identifies specific conditions where the methods degrade:
  • High Noise: When noise ($\sigma$) is high relative to the arm gap, fingerprints become weak, and non-stationary baselines (like D-UCB) may perform better.
  • Weak Fingerprint Separation: If different states yield similar joint reward distributions, the probing strategy cannot disambiguate them.
  • Fast Switching: Sequential probing (SP-UCB) fails when the state changes frequently within the probe window (low $p_{stay}$), as the synthetic fingerprint becomes invalid.
• Ablation Studies: Removing the fingerprint feature ($\phi_{fp}$) significantly increased regret in sticky-state environments, confirming the value of joint observations. Removing the lagged context ($\phi_{lag}$) had a smaller impact in some randomized settings, suggesting adaptive timing was the primary driver of improvement there.

5. Significance and Claims

The paper claims that its primary contribution is a practical approach to structured non-stationarity where the environment evolves via an autonomous Markov process. Unlike standard non-stationary bandits that treat changes as arbitrary drift, or Partially Observable MDPs (POMDPs) that require full observability or complex decoding, this approach uses lightweight history summaries and probes to maintain a current estimate of the optimal arm.

The authors emphasize that their methods are most effective in regimes where:

1. The latent state is predictable over short horizons (slow mixing).
2. The probing strategy can generate sufficient statistics (fingerprints) that separate the relevant states.
3. The adaptive gating mechanisms can keep these summaries current without incurring excessive probe regret.

The work bridges the gap between contextual bandits and latent-state reinforcement learning by offering a computationally efficient solution (based on LinUCB) that does not require learning the full transition dynamics of the hidden state.