Combinatorial Semi-Bandit in the Non-Stationary Environment

Abstract

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 \cite{wang2017improving}, our algorithm achieves $\tilde{\mathcal{O}}(\sqrt{\mathcal{S}T})$ distribution-dependent regret in the switching case, and $\tilde{\mathcal{O}}({\mathcal{V}}^{1/3}{T}^{2/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.

arXiv commentAccepted to UAI 2021

References in corpus (16)

• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• The on-line shortest path problem under partial monitoring
• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Combinatorial Bandits Revisited
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Cascading Bandits: Learning to Rank in the Cascade Model
• Efficient Contextual Bandits in Non-stationary Worlds
• Combinatorial Multi-Armed Bandit with General Reward Functions
• Combinatorial Cascading Bandits
• Weighted Linear Bandits for Non-Stationary Environments
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Tracking the Best Expert in Non-stationary Stochastic Environments
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
• A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Online Second Price Auction with Semi-bandit Feedback Under the Non-Stationary Setting

Cited by in corpus (3)

• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits