Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals
2026-06-12 • Machine Learning
Machine Learning
AI summaryⓘ
The authors introduce new methods to efficiently find best patterns in large connected data by learning the hidden relationships in the data. Their approach uses advanced mathematical tools like graphs, kernel methods, and Taylor approximations to model cause-and-effect structures. They provide proofs that their method works well over time and is robust to noise and errors. They also test their approach on both simulated and real transportation data to show it can work in practice.
causal modelinggraph theoryreproducing kernel methodsTaylor approximationnonlinear statisticstime complexityrobustnessdata samplingmodel convergence
Authors
Christoph Bauschmann, Setareh Maghsudi
Abstract
The identification of optimal structures within vast arrays of interconnected data necessitates significant sampling- and computational effort. Learning and leveraging underlying signal dependencies can improve efficiency and predictive capabilities considerably, but the ubiquity of nonlinear statistical relations amplifies the complexity of such undertakings. In this paper, we develop novel generic and adaptive strategies equipped with routines for graph-based causal reward modeling, analytic reproducing kernel methods, and Taylor approximation of functional processes. We establish theoretical performance guarantees sublinear in time and linear in data volume over time. Our analyses cover robustness to a multitude of uncertainties arising from noise interference, gradual model convergence, and solution space mismatch. The framework's general appeal is substantiated by a minimalistic set of conditions or reliance on prior estimates, while various outlined modifications address specific or extended settings. To demonstrate practical effectiveness, we conduct numerical experiments using both benchmarked synthetic and real-world transportation datasets.