Online Learning for Multi-Layer Hierarchical Inference under Partial and Policy-Dependent Feedback
This work is significant for researchers and practitioners working with multi-layer hierarchical inference systems, particularly in scenarios with partial and policy-dependent feedback, by providing a more stable and performant online learning algorithm.
This paper addresses the challenge of learning optimal routing policies in multi-layer hierarchical inference systems where feedback on prediction error is only available at the terminal layer. The authors develop a variance-reduced EXP4-based algorithm integrated with Lyapunov optimization, which achieves unbiased loss estimation and stable learning under sparse and policy-dependent feedback, outperforming standard importance-weighted approaches on large-scale multi-task workloads.
Hierarchical inference systems route tasks across multiple computational layers, where each node may either finalize a prediction locally or offload the task to a node in the next layer for further processing. Learning optimal routing policies in such systems is challenging: inference loss is defined recursively across layers, while feedback on prediction error is revealed only at a terminal oracle layer. This induces a partial, policy-dependent feedback structure in which observability probabilities decay with depth, causing importance-weighted estimators to suffer from amplified variance. We study online routing for multi-layer hierarchical inference under long-term resource constraints and terminal-only feedback. We formalize the recursive loss structure and show that naive importance-weighted contextual bandit methods become unstable as feedback probability decays along the hierarchy. To address this, we develop a variance-reduced EXP4-based algorithm integrated with Lyapunov optimization, yielding unbiased loss estimation and stable learning under sparse and policy-dependent feedback. We provide regret guarantees relative to the best fixed routing policy in hindsight and establish near-optimality under stochastic arrivals and resource constraints. Experiments on large-scale multi-task workloads demonstrate improved stability and performance compared to standard importance-weighted approaches.