mlsanityData to 7 Oct 2026

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

arXiv 2606.14650 ↗First posted 12 Jun 2026cs.LGcited by 0

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 19 of its 27 references that are in the map. First posted on arXiv 12 Jun 2026.

Builds on

19 of 27 references.

References · 19

  1. 2017On Kernelized Multi-armed Banditscited by 348
  2. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  3. 2016Combinatorial Multi-Armed Bandit with General Reward Functionscited by 56
  4. 2021Causal Bandits with Unknown Graph Structurecited by 37
  5. 2022Causal Bandits for Linear Structural Equation Modelscited by 19
  6. 2023Combinatorial Stochastic-Greedy Banditcited by 18
  7. 2022Combinatorial Causal Banditscited by 16
  8. 2023Combinatorial Neural Banditscited by 16
  9. 2020Tight Lower Bounds for Combinatorial Multi-Armed Banditscited by 15
  10. 2022Mixed-Effect Thompson Samplingcited by 14
  11. 2023Causal Bandits without Graph Learningcited by 10
  12. 2024Causal Bandits with General Causal Models and Interventionscited by 7
7 more
  1. 2021Neural Architecture Search via Combinatorial Multi-Armed Banditcited by 5
  2. 2023Online Learning with Feedback Graphs: The True Shape of Regretcited by 5
  3. 2024Linear Causal Bandits: Unknown Graph and Soft Interventionscited by 5
  4. 2022Linear Combinatorial Semi-Bandit with Causally Related Rewardscited by 4
  5. 2024Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Banditscited by 3
  6. 2023Non-stationary Delayed Combinatorial Semi-Bandit with Causally Related Rewardscited by 1
  7. 2023Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewardscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022Semi-Parametric Contextual Bandits with Graph-Laplacian Regularization
  2. 2023Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws
  3. 2024Transductive Reward Inference on Graph
  4. 2026BFTS: Thompson Sampling with Bayesian Additive Regression Trees
  5. 2026Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
  6. 2024Linear Contextual Bandits with Hybrid Payoff: Revisited
  7. 2023Causal Structural Learning from Time Series: A Convex Optimization Approach
  8. 2025Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown