Lune

NeurIPS2024Top-tier venue

No-Regret Bandit Exploration based on Soft Tree Ensemble Model

Shogo Iwazaki, Shinya Suzumura

Abstract

We propose a novel stochastic bandit algorithm that employs reward estimates using a tree ensemble model. Specifically, our focus is on a soft tree model, a variant of the conventional decision tree that has undergone both practical and theoretical scrutiny in recent years. By deriving several non-trivial properties of soft trees, we extend the existing analytical techniques used for neural bandit algorithms to our soft tree-based algorithm. We demonstrate that our algorithm achieves a smaller cumulative regret compared to the existing ReLU-based neural bandit algorithms. We also show that this advantage comes with a trade-off: the hypothesis space of the soft tree ensemble model is more constrained than that of a ReLU-based neural network. Recently, Kanoh and Sugiyama [21] generalized the NTK theory to the soft tree ensemble model. Let g(x, θ) := ∇ θ h(x; θ) ∈ R p be the gradient vector of the soft tree ensemble model at parameter

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Neural Thompson Sampling cites Neural Contextual Bandits with UCB-based Exploration
  • Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere cites Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits
  • Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere cites Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
  • Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere cites Neural Contextual Bandits with UCB-based Exploration
  • Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits cites Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian OptimizationShogo IwazakiNeurIPS 2025 · 16 citations
  2. Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process BanditsShogo IwazakiNeurIPS 2025 · 10 citations
  3. Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in HypersphereShogo IwazakiICML 2026 · 5 citations

Builds on11

  1. Neural Oblivious Decision Ensembles for Deep Learning on Tabular DataSergei Popov, Stanislav Morozov, Artem BabenkoICLR 2020 · 407 citations
  2. Neural Contextual Bandits with UCB-based ExplorationDongruo Zhou, Lihong Li, Quanquan GuICML 2020 · 329 citations
  3. On the linearity of large non-linear models: when and why the tangent kernel is constantChaoyue Liu, Libin Zhu, Mikhail BelkinNeurIPS 2020 · 183 citations
  4. Neural Thompson SamplingWeitong Zhang, Dongruo Zhou, Lihong Li, Quanquan GuICLR 2021 · 152 citations
  5. The Tree Ensemble Layer: Differentiability meets Conditional ComputationHussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan et al.ICML 2020 · 95 citations

Related papers

  1. A Neural Tangent Kernel Perspective of Infinite Tree EnsemblesRyuichi Kanoh, Mahito SugiyamaICLR 2022 · 7 citations
  2. Stochastic Bandits with ReLU Neural NetworksKan Xu, Hamsa Bastani, Surbhi Goel, Osbert BastaniICML 2024 · 1 citation
  3. Neural Contextual Bandits with Deep Representation and Shallow ExplorationPan Xu, Zheng Wen, Handong Zhao, Quanquan GuICLR 2022 · 90 citations
  4. Neural Tangent Kernels for Axis-Aligned Tree EnsemblesRyuichi Kanoh, Mahito SugiyamaICML 2024
  5. Analyzing Tree Architectures in Ensembles via Neural Tangent KernelRyuichi Kanoh, Mahito SugiyamaICLR 2023
Dusk over the sea between two cliffs drawn in fine vertical lines