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

arXiv: https://arxiv.org/abs/2606.14650 · HTML: https://mlsanity.com/paper/2606.14650/

## Key facts

- No citing papers in the map yet (data through 14 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.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 19 of 19)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Causal Bandits with Unknown Graph Structure](https://mlsanity.com/paper/2106.02988/) (2021)
- [Causal Bandits for Linear Structural Equation Models](https://mlsanity.com/paper/2208.12764/) (2022)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Combinatorial Causal Bandits](https://mlsanity.com/paper/2206.01995/) (2022)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Causal Bandits without Graph Learning](https://mlsanity.com/paper/2301.11401/) (2023)
- [Causal Bandits with General Causal Models and Interventions](https://mlsanity.com/paper/2403.00233/) (2024)
- [Neural Architecture Search via Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2101.00336/) (2021)
- [Online Learning with Feedback Graphs: The True Shape of Regret](https://mlsanity.com/paper/2306.02971/) (2023)
- [Linear Causal Bandits: Unknown Graph and Soft Interventions](https://mlsanity.com/paper/2411.02383/) (2024)
- [Linear Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2212.12923/) (2022)
- [Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2402.15171/) (2024)
- [Non-stationary Delayed Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.09093/) (2023)
- [Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.14138/) (2023)

## 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.