Learning to Defer in Non-Stationary Time Series via Switching State-Space Models

Technical Summary: Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Models

Problem Formulation
The paper addresses the challenge of Learning-to-Defer (L2D) in streaming, non-stationary time-series environments. Unlike offline L2D settings which assume full supervision (access to all expert predictions) and a fixed internal predictor, the proposed setting involves:

1. Asymmetric Partial Feedback: At each round $t$, the system observes the context $x_t$ and a set of available external experts $E_t$. It must choose to either predict internally (action 0) or defer to an external expert $k \in E_t$ (incurring a query cost $\beta_k$). Crucially, the true outcome $y_t$ is revealed after the decision, making the internal residual ($e_{t,0} = \hat{y}_{t,0} - y_t$) always observable. However, external residuals are only observed if the corresponding expert is queried; otherwise, they remain censored.
2. Action-Coupled Learning: The internal predictor $f_{\theta_t}$ is trained online. Routing decisions directly influence the learner's future state because querying an expert provides an additional "teacher" signal ($\hat{y}_{t,k}$) that can update the internal model.
3. Non-Stationarity and Dynamic Expertise: The environment is non-stationary, with expert quality shifting across latent regimes. Furthermore, the pool of experts is dynamic; experts may enter, leave, or return over time.

The objective is to minimize the expected cumulative routing cost, balancing immediate prediction error against query costs, while simultaneously improving the internal learner and adapting to regime shifts.

Methodology: L2D-SLDS
The authors propose L2D-SLDS, a one-stage online framework that jointly models the residuals of the internal predictor and all potential external experts using a factorized Switching Linear-Gaussian State-Space Model (SLDS).

• Generative Model: The model decomposes the latent reliability of each expert $k$ into three components:

  1. A shared global factor $g_t$ that captures cross-expert correlations and transfers information across the expert pool.
  2. Per-expert idiosyncratic states $u_{t,k}$ that capture expert-specific reliability.
  3. A discrete regime variable $z_t$ that selects among $M$ linear-Gaussian dynamics, allowing the system to adapt to structural changes in expert performance.
     The residual for expert $k$ is modeled as a linear-Gaussian emission of the reliability vector $\alpha_{t,k} = B_k g_t + u_{t,k}$.

• Online Inference: The system employs an IMM-style (Interacting Multiple Model) two-phase filter:

  1. Internal Phase: Always executed. It incorporates the always-observed internal residual $e_{t,0}$ to update the shared factor $g_t$ and regime weights. This ensures that even when no external expert is queried, the system updates its beliefs about all unqueried experts via the shared factor.
  2. External Phase: Executed only if an external expert is queried. It incorporates the observed external residual to further refine the specific expert's state and the global factor.
  3. Registry Management: A dynamic registry handles expert births and deaths. Stale experts (unavailable for a duration $\Delta_{max}$) are pruned via exact marginalization, ensuring computational and memory efficiency without affecting the predictive distributions of retained experts.

• Learner-Aware Routing Score: The routing decision is driven by a score $S_t(k)$ that balances three objectives:

  1. Exploitation: The immediate excess cost of querying expert $k$ versus the internal predictor.
  2. Exploration (Information Gain): The conditional mutual information $I((z_t, g_t); e_{t,k} | e_{t,0})$, measuring how much the query reduces uncertainty about the latent state beyond what the internal residual already provides. This is approximated via a closed-form term for the shared factor and a Monte Carlo term for regime identification.
  3. Learner Improvement: An estimate of the expected one-step improvement to the internal learner, based on the probability that the expert will outperform the internal predictor and the magnitude of that improvement.

• Action-Coupled Update: When an expert is queried, the internal learner is updated using a teacher-regularized objective. The weight of the teacher signal is adaptive, gating updates based on the expert's predicted reliability, realized helpfulness, and disagreement with the learner.

Key Contributions

1. Formalization: The paper formalizes one-stage online L2D for non-stationary time series, explicitly handling asymmetric partial feedback, action-coupled internal learning, dynamic expert availability, and consultation costs.
2. Algorithm: It introduces L2D-SLDS, a factorized switching linear-Gaussian model that enables scalable inference and cross-expert information transfer under censorship. It includes a registry pruning mechanism that preserves the marginal distributions of retained experts.
3. Routing Strategy: A novel learner-aware query score is proposed, combining latent-state information gain with expected learner improvement, moving beyond simple cost-minimization or pure exploration.
4. Theoretical Guarantees: The authors prove an oracle regret decomposition against a time-varying learn-and-defer comparator. The regret is decomposed into a query-bonus budget, an SLDS predictive-cost-error term ($E_{SLDS}$), and the internal learner's interval dynamic regret. Under specific conditions (sublinear $E_{SLDS}$ and certified internal learners), they establish a sublinear realized regret rate.
5. Empirical Performance: Extensive experiments on synthetic data and real-world benchmarks (Melbourne, Jena, Delhi) demonstrate that L2D-SLDS outperforms contextual and non-stationary bandit baselines while deferring on less than 2% of rounds in real-data scenarios.

Results

• Synthetic Data: L2D-SLDS achieved the lowest routing cost (0.336) compared to the best bandit baseline (0.427). Ablation studies confirmed that the shared factor $g_t$ is critical for information transfer, as removing it degraded performance.
• Real-World Benchmarks:
  • Melbourne: L2D-SLDS achieved a cost of 5.914 with a 0.8% deferral rate, outperforming all bandit baselines (which ranged from 6.047 to 6.302 and had higher deferral rates).
  • Jena: L2D-SLDS achieved 3.293 with a 0.22% deferral rate. Notably, it was the only adaptive method to improve upon the non-deferring internal predictor (3.297), whereas all bandit baselines performed worse than the non-deferring baseline.
  • Delhi (24 Experts): L2D-SLDS achieved 2.528 with a 1.70% deferral rate. The strongest bandit baseline (SharedLinUCB+0) achieved 2.542 but required a 34.8% deferral rate, highlighting L2D-SLDS's efficiency in selecting high-value deferrals.
• Ablations: Removing the shared factor or replacing the information-directed score with Thompson sampling significantly degraded performance or increased query rates, validating the specific design choices of the model and scoring mechanism.

Significance and Claims
The paper claims to be the first work to jointly train an internal learner and route to external experts online under asymmetric feedback, latent regime switches, and dynamic expert registries. The significance lies in demonstrating that a probabilistic model of residuals can effectively handle the "censored" nature of expert feedback in non-stationary settings, allowing the system to learn about unqueried experts through a shared latent structure. The authors emphasize that their approach achieves competitive or superior performance with drastically lower query rates compared to standard bandit approaches, making it suitable for high-stakes or cost-sensitive applications where deferral is expensive. The theoretical regret decomposition provides a modular framework for understanding the trade-offs between exploration, prediction error, and learner adaptation.