Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals

• URL: http://arxiv.org/abs/2606.14650v1
• Date: Fri, 12 Jun 2026 17:11:56 GMT
• Title: Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals
• Abstract summary: We develop novel generic and adaptive strategies equipped with routines for graph-based causal reward modeling.<n>We establish theoretical performance guarantees sublinear in time and linear in data volume over time.<n>We conduct numerical experiments using both benchmarked synthetic and real-world transportation datasets.
• Score: 9.51084845180104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Adaptive Recurrent Message Passing for Test Time Computing on Graphs [80.56829418752513]
  We show that recurrent graph models can overcome the intrinsic mismatch between graph data and architectural designs.<n>We propose AdaR, an Adaptive Recurrent graph model, empowering flexible test-time computing on various downstream tasks without changing model parameters.
  arXiv  Detail & Related papers  (2026-06-21T12:14:11Z)
• Structured Nonparametric Variational Inference for Dependent Latent Modeling [11.146941243243248]
  Variational inference (VI) is a core engine of modern AI, enabling scalable learning and uncertainty-aware training of large probabilistic and generative models.<n>We propose Structured Non Variational Inference (SN-VI), a novel framework for modeling complex dependencies among latent variables in posterior approximation.<n> SN-VI preserves intricate latent variable dependencies, providing a flexible and accurate approximation of posterior boundeds with arbitrary shapes.
  arXiv  Detail & Related papers  (2026-06-13T20:29:04Z)
• Modeling Nonlinear Feature Interactions with Product-Unit Residual Networks [0.9367224590861915]
  Product-unit residual networks (PURe) integrate multiplicative product units with residual connections to explicitly model cross-feature couplings.<n>We conduct a systematic evaluation on an interaction-driven synthetic benchmark and two real-world datasets.<n> PURe achieves competitive or improved performance, better robustness and sample efficiency in low-data regimes, and enhanced interaction-level interpretability.
  arXiv  Detail & Related papers  (2026-06-05T03:11:08Z)
• Bridging Training and Merging Through Momentum-Aware Optimization [8.035521056416242]
  Training large neural networks and task-specific computation models require parameter importance estimation.<n>Current compute curvature information during training, discard it, then recompute similar information for merging.<n>We introduce a unified framework that factorized momentum and curvature statistics during training, then recompute similar information for merging.
  arXiv  Detail & Related papers  (2025-12-18T22:37:33Z)
• Topology Identification and Inference over Graphs [61.06365536861156]
  Topology identification and inference of processes evolving over graphs arise in timely applications involving brain, transportation, financial, power, as well as social and information networks.<n>This chapter provides an overview of graph topology identification and statistical inference methods for multidimensional data.
  arXiv  Detail & Related papers  (2025-12-11T00:47:09Z)
• Semi-parametric Functional Classification via Path Signatures Logistic Regression [1.210026603224224]
  We propose Path Signatures Logistic Regression, a semi-parametric framework for classifying vector-valued functional data.<n>Our results highlight the practical and theoretical benefits of integrating rough path theory into modern functional data analysis.
  arXiv  Detail & Related papers  (2025-07-09T08:06:50Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Efficient Interpretable Nonlinear Modeling for Multiple Time Series [5.448070998907116]
  This paper proposes an efficient nonlinear modeling approach for multiple time series. It incorporates nonlinear interactions among different time-series variables. Experimental results show that the proposed algorithm improves the identification of the support of the VAR coefficients in a parsimonious manner.
  arXiv  Detail & Related papers  (2023-09-29T11:42:59Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  Three major challenges in reinforcement learning are the complex dynamical systems with large state spaces, the costly data acquisition processes, and the deviation of real-world dynamics from the training environment deployment. We study distributionally robust Markov decision processes with continuous state spaces under the widely used Kullback-Leibler, chi-square, and total variation uncertainty sets. We propose a model-based approach that utilizes Gaussian Processes and the maximum variance reduction algorithm to efficiently learn multi-output nominal transition dynamics.
  arXiv  Detail & Related papers  (2023-09-05T13:42:11Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies. A neural network is employed to act as structure prior and reveal the underlying signal interdependencies. Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
  arXiv  Detail & Related papers  (2022-03-29T21:00:39Z)
• Multiplicative noise and heavy tails in stochastic optimization [62.993432503309485]
  empirical optimization is central to modern machine learning, but its role in its success is still unclear. We show that it commonly arises in parameters of discrete multiplicative noise due to variance. A detailed analysis is conducted in which we describe on key factors, including recent step size, and data, all exhibit similar results on state-of-the-art neural network models.
  arXiv  Detail & Related papers  (2020-06-11T09:58:01Z)
• Dynamic Federated Learning [57.14673504239551]
  Federated learning has emerged as an umbrella term for centralized coordination strategies in multi-agent environments. We consider a federated learning model where at every iteration, a random subset of available agents perform local updates based on their data. Under a non-stationary random walk model on the true minimizer for the aggregate optimization problem, we establish that the performance of the architecture is determined by three factors, namely, the data variability at each agent, the model variability across all agents, and a tracking term that is inversely proportional to the learning rate of the algorithm.
  arXiv  Detail & Related papers  (2020-02-20T15:00:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.