# Combinatorial Rising Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 34 references that are in the map.
- First posted on arXiv 1 Dec 2024.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Progressive-Hint Prompting Improves Reasoning in Large Language Models](https://mlsanity.com/paper/2304.09797/) (2023)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Combinatorial Semi-Bandit in the Non-Stationary Environment](https://mlsanity.com/paper/2002.03580/) (2020)
- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [Scalable Neural Contextual Bandit for Recommender Systems](https://mlsanity.com/paper/2306.14834/) (2023)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Best Arm Identification for Stochastic Rising Bandits](https://mlsanity.com/paper/2302.07510/) (2023)
- [Neural Architecture Search via Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2101.00336/) (2021)
- [Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback](https://mlsanity.com/paper/2305.16074/) (2023)
- [Observation-Augmented Contextual Multi-Armed Bandits for Robotic Search and Exploration](https://mlsanity.com/paper/2312.12583/) (2023)
- [Unsupervised Skill Discovery for Robotic Manipulation through Automatic Task Generation](https://mlsanity.com/paper/2410.04855/) (2024)
- [Multi-Task Combinatorial Bandits for Budget Allocation](https://mlsanity.com/paper/2409.00561/) (2024)
- [Neural Combinatorial Clustered Bandits for Recommendation Systems](https://mlsanity.com/paper/2410.14586/) (2024)
- [Rising Rested Bandits: Lower Bounds and Efficient Algorithms](https://mlsanity.com/paper/2411.14446/) (2024)

## Built on by (most cited first, 1 of 1)

- [Rising Multi-Armed Bandits with Known Horizons](https://mlsanity.com/paper/2602.10727/) (2026)

## Abstract (arXiv)

Combinatorial online learning is a fundamental task for selecting the optimal action (or super arm) as a combination of base arms in sequential interactions with systems providing stochastic rewards. It is applicable to diverse domains such as robotics, social advertising, network routing, and recommendation systems. In many real-world scenarios, we often encounter rising rewards, where playing a base arm not only provides an instantaneous reward but also contributes to the enhancement of future rewards, e.g., robots improving through practice and social influence strengthening in the history of successful recommendations. Crucially, these enhancements may propagate to multiple super arms that share the same base arms, introducing dependencies beyond the scope of existing bandit models. To address this gap, we introduce the Combinatorial Rising Bandit (CRB) framework and propose a provably efficient and empirically effective algorithm, Combinatorial Rising Upper Confidence Bound (CRUCB). We empirically demonstrate the effectiveness of CRUCB in realistic deep reinforcement learning environments and synthetic settings, while our theoretical analysis establishes tight regret bounds. Together, they underscore the practical impact and theoretical rigor of our approach. Our code is available at https://github.com/ml-postech/Combinatorial-Rising-Bandits.