Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits

Non-stationary multi-armed bandits (NSMAB) enable agents to adapt to changing environments by incorporating mechanisms to detect and respond to shifts in reward distributions, making them well-suited for dynamic settings. However, existing approaches typically assume that reward feedback is available at every round--an assumption that overlooks many real-world scenarios where feedback is limited. In this paper, we take a significant step forward by introducing a new model of constrained feedback in non-stationary multi-armed bandits (CONFEE-NSMAB), where the availability of reward feedback is restricted. We propose the first priorfree algorithm--that is, one that does not require prior knowledge of the degree of non-stationarity--that achieves near-optimal dynamic regret in this setting. Specifically, our algorithm attains a dynamic regret of O(K1/3V1/3TT/B1/3), where T is the number of rounds, K is the number of arms, B is the query budget, and VT is the variation budget capturing the degree of non-stationarity.