Online Learning for Multi-Layer Hierarchical Inference under Partial and Policy-Dependent Feedback

Researchers developed a new variance-reduced EXP4-based algorithm for optimizing routing policies in multi-layer hierarchical inference systems. The solution addresses the challenge of sparse, policy-dependent feedback in AI systems where prediction errors are only revealed at terminal layers, improving stability and performance over standard importance-weighted approaches.

• →Multi-layer hierarchical inference systems face challenges with partial feedback that only occurs at terminal oracle layers.
• →Standard importance-weighted contextual bandit methods become unstable as feedback probability decays along the hierarchy.
• →A new variance-reduced EXP4-based algorithm integrated with Lyapunov optimization provides unbiased loss estimation.
• →The algorithm demonstrates improved stability and performance on large-scale multi-task workloads compared to existing approaches.
• →The research provides regret guarantees and establishes near-optimality under stochastic arrivals and resource constraints.