MNL-Bandit in non-stationary environments
This addresses the challenge of dynamic decision-making in multi-armed bandit settings for applications like online advertising, though it is incremental as it builds on prior stationary work.
The paper tackles the MNL-Bandit problem in non-stationary environments by developing an algorithm with a worst-case expected regret of ˜O(min{√(NTL), N^(1/3)(Δ_∞^K)^(1/3)T^(2/3) + √(NT)}), and proves matching lower bounds to show optimality.
In this paper, we study the MNL-Bandit problem in a non-stationary environment and present an algorithm with a worst-case expected regret of $\tilde{O}\left( \min \left\{ \sqrt{NTL}\;,\; N^{\frac{1}{3}}(Δ_{\infty}^{K})^{\frac{1}{3}} T^{\frac{2}{3}} + \sqrt{NT}\right\}\right)$. Here $N$ is the number of arms, $L$ is the number of changes and $Δ_{\infty}^{K}$ is a variation measure of the unknown parameters. Furthermore, we show matching lower bounds on the expected regret (up to logarithmic factors), implying that our algorithm is optimal. Our approach builds upon the epoch-based algorithm for stationary MNL-Bandit in Agrawal et al. 2016. However, non-stationarity poses several challenges and we introduce new techniques and ideas to address these. In particular, we give a tight characterization for the bias introduced in the estimators due to non stationarity and derive new concentration bounds.