# Combinatorial Semi-Bandit in the Non-Stationary Environment

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2020.

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

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024)
- [MNL-Bandit in non-stationary environments](https://mlsanity.com/paper/2303.02504/) (2023)
- [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)
- [Learning to Schedule in Non-Stationary Wireless Networks With Unknown Statistics](https://mlsanity.com/paper/2308.02734/) (2023)
- [Combinatorial Rising Bandits](https://mlsanity.com/paper/2412.00798/) (2024)
- [Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2509.15073/) (2025)
- [Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses](https://mlsanity.com/paper/2602.07418/) (2026)
- [Exploring Multiple High-Scoring Subspaces in Generative Flow Networks](https://mlsanity.com/paper/2602.11491/) (2026)
- [Learning to Control under Time-Varying Environment](https://mlsanity.com/paper/2206.02507/) (2022)
- [BORA: Bayesian Optimization for Resource Allocation](https://mlsanity.com/paper/2210.05977/) (2022)
- [Finite-Time Guarantees for Multi-Agent Combinatorial Bandits with Nonstationary Rewards](https://mlsanity.com/paper/2508.20923/) (2025)
- [Multi-Play Combinatorial Semi-Bandit Problem](https://mlsanity.com/paper/2509.09933/) (2025)
- [Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary](https://mlsanity.com/paper/2609.13547/) (2026)

## Abstract (arXiv)

In this paper, we investigate the non-stationary combinatorial semi-bandit problem, both in the switching case and in the dynamic case. In the general case where (a) the reward function is non-linear, (b) arms may be probabilistically triggered, and (c) only approximate offline oracle exists citewang2017improving, our algorithm achieves tildeO(√S T) distribution-dependent regret in the switching case, and tildeO(V1/3T2/3) in the dynamic case, where mathcal S is the number of switchings and mathcal V is the sum of the total ``distribution changes''. The regret bounds in both scenarios are nearly optimal, but our algorithm needs to know the parameter mathcal S or mathcal V in advance. We further show that by employing another technique, our algorithm no longer needs to know the parameters mathcal S or mathcal V but the regret bounds could become suboptimal. In a special case where the reward function is linear and we have an exact oracle, we design a parameter-free algorithm that achieves nearly optimal regret both in the switching case and in the dynamic case without knowing the parameters in advance.