Research map / Bandits and online learning / Contextual bandits and Thompson sampling
No-Regret Bandit Exploration based on Soft Tree Ensemble Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ST-UCB, a UCB bandit using a soft tree ensemble reward model with tree neural tangent kernel theory, proving a no-regret O~(sqrt(T)) bound and comparing favorably to ReLU neural bandits on synthetic and UCI energy data.
Problem
Stochastic bandits with large action spaces need reward models whose uncertainty can be analyzed; existing neural bandit (NN-UCB) regret bounds with ReLU networks are super-linear in general action sets, so no-regret guarantees are lacking.
Approach
Replace the ReLU network reward estimator with a soft tree ensemble, use its tree neural tangent kernel (TNTK) to derive eigendecay, concentration, and Hessian bounds, and obtain a maximum information gain of O(ln^d T) yielding a sqrt(T)-scale regret bound in a UCB algorithm.
Key results
- ST-UCB achieves regret O~(sqrt(T)) with maximum information gain O(ln^d T) for TNTK, versus super-linear growth for ReLU NN-UCB.
- On synthetic f(1) and f(2), ST-UCB outperforms NN-UCB, ST-greedy and NN-greedy in cumulative regret.
- On the real-world energy dataset, ST-UCB has higher regret early but flatter cumulative regret growth later, with no clear advantage in early rounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ST-UCB with a soft tree ensemble instead of NN-UCB with a ReLU network | Bandit exploration · Synthetic dataset, f (1)(x) = 10(x⊤a)² and f (2)(x) = x⊤A⊤Ax | cumulative regret | Helped |
| Use ST-UCB with a soft tree ensemble instead of NN-UCB with a ReLU network | Bandit exploration · Synthetic dataset, f (3)(x) = cos(3x⊤a) | cumulative regret | No clear effect |
| Use ST-UCB with a soft tree ensemble instead of the other policies | Bandit exploration · Energy Efficiency dataset, ˜K = 20, 40, and 60 | cumulative regret | Mixed |
Surprising findings
- ST-UCB has higher cumulative regret than baselines in early rounds on the real-world dataset.
Limitations
- Analysis assumes fixed scaling parameter alpha; hard-tree limit (alpha to infinity) not covered by guarantees.
- Hypothesis space induced by TNTK is more constrained than the ReLU NTK space.
- Learning uses gradient descent on soft trees rather than common greedy hard-tree learning; theory does not cover ensemble learning methods.
Experimental setup
Datasets: Energy Efficiency (UCI) synthetic bandit reward functions f(1), f(2), f(3)
Benchmarks: Energy Efficiency (UCI) bandit synthetic bandit functions f(1), f(2), f(3)
Metrics: cumulative regret
Baselines: NN-UCB NN-greedy ST-greedy
Builds on: NN-UCB tree neural tangent kernel kernelized UCB Kanoh and Sugiyama soft tree NTK
Closest papers by meaning
- Stochastic Bandits with ReLU Neural Networks (ICML 2024 · similarity 0.89)
- On Kernelized Multi-Armed Bandits with Constraints (NeurIPS 2022 · similarity 0.88)
- Neural Combinatorial Clustered Bandits for Recommendation Systems (AAAI 2025 · similarity 0.87)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.86)
- Ensemble sampling for linear bandits: small ensembles suffice (NeurIPS 2024 · similarity 0.86)
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.