Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits

Shaoang Li, Jian Li · 2025

Read Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits by Shaoang Li, Jian Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15073.txt.

Introduction

Shaoang Li and Jian Li study learning with scarce feedback in changing environments in a 2025 machine learning theory paper. Multi-armed bandits model the choice among options with unknown rewards, and non-stationary versions let those rewards drift over time. Most algorithms assume the learner sees the reward after every round, which many real systems cannot afford.

Their new model restricts how often feedback may be requested, under a fixed query budget. They propose the first algorithm that needs no prior knowledge of how fast the environment changes. It still achieves near-optimal dynamic regret, the gap against an oracle that always picks the best arm. The regret bound depends on the number of arms, the total variation of the environment, the time horizon, and the budget. Limited feedback, handled well, need not cripple adaptation.

Catalog record

CREATORShaoang Li, Jian Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE87 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-15073

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits Shaoang Li, Jian Li Abstract 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 prior-free 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 𝒪 ~ ​ ( K 1 / 3 ​ V T 1 / 3 ​ T / B 1 / 3 ) \tilde{\mathcal{O}}({K^{1/3}V_{T}^{1/3}T}/{B^{1/3}}) , where T T is the number of rounds, K K is the number of arms, B B is the query budget, and V T V_{T} is the variation budget capturing the degree of non-stationarity. 1 Introduction The multi-armed bandits (MAB) problem [ 29 ] is a fundamental framework for decision-making under uncertainty, where an agent selects from a set of arms to maximize cumulative rewards over a time horizon, balancing exploration (learning about arms) and exploitation (leveraging known rewards). Most state-of-the-art MAB algorithms, including Upper Confidence Bound (UCB)-type methods [ 1 ] and Thompson Sampling (TS)-based approaches [ 34 ] , assume stationary settings in which reward distributions remain fixed over time. However, many real-world applications—such as dynamic pricing [ 14 ] , evolving user preferences [ 21 ] , and environmental shifts [ 16 ] —are inherently non-stationary, with reward distributions that change over time. This has led to growing interest in non-stationary MAB ( nsMAB ), which incorporates mechanisms for detecting and adapting to such changes, making it more applicable to dynamic environments. However, most of the existing literature on nsMAB assumes that reward feedback is available to the agent at every round. This overlooks a critical aspect of many real-world applications, where feedback is often limited. For example, in recommendation systems, repeatedly asking users for feedback on the quality of recommendations can lead to user fatigue or annoyance [ 13 ] . Similarly, in reinforcement learning from human feedback (RLHF) [ 11 ] , essential signals such as preference comparisons, demonstrations, or ratings are often costly, time-consuming, or constrained by the availability of expert annotators. Motivated by these challenges, we introduce a new model of constrained feedback in non-stationary multi-armed bandits , termed ConFee-nsMAB , in which the availability of reward feedback is limited. Similar to existing nsMAB frameworks, ConFee-nsMAB quantifies the degree of non-stationarity in the environment by tracking changes in reward distributions and assumes that the variation in mean rewards over the time horizon T is bounded by a variation budget V_{T} [ 5 ] . However, unlike conventional nsMAB , the agent in ConFee-nsMAB cannot observe reward feedback at every round. Instead, the total number of reward feedback queries available to the agent over the time horizon T is limited by a reward query budget B . This constraint provides the agent with significantly less information than in standard nsMAB settings, making the ConFee-nsMAB problem fundamentally more challenging. Motivated by this, the primary question we seek to address is: How does the reward feedback querying constraint affect the agent’s decision-making process in ConFee-nsMAB , particularly in balancing exploration, exploitation, and query efficiency under limited feedback? Despite recent advances in feedback-constrained MAB [ 13 , 26 ] and prior-free 1 1 1 The algorithm operates without prior knowledge of the degree of non-stationarity, making it more practical and broadly applicable. non-stationary RL or MAB [ 37 ] , this question remains, to the best of our knowledge, unexplored in the context of constrained feedback learning for nsMAB (see Table 1 ). In this setting, the agent faces a unique dilemma: balancing exploration and exploitation in non-stationary environments while operating under a strict feedback query constraint. This introduces a new layer of complexity to the already challenging problem of designing prior-free algorithms for nsMAB with near-optimal dynamic regret 2 2 2 In non-stationary settings, the conventional “static regret”, defined with respect to a single best action, may perform poorly. Instead, “dynamic regret” is the appropriate performance metric [ 5 ] . See Section 2 for a detailed definition. guarantees. This leads us to the second research question: Is it possible to design prior-free algorithms for ConFee-nsMAB that achieve near-optimal dynamic regret guarantees? Motivated by these open questions, we make the following key contributions: Paper Setting Variation V_{T} Constrained Feedback Upper Bound Lower Bound Besbes et al. 2014 Non-Stationary Known ✗ \tilde{\mathcal{O}}(K^{1/3}V_{T}^{1/3}T^{2/3}) \Omega(K^{1/3}V_{T}^{1/3}T^{2/3}) Wei and Luo 2021 Non-Stationary Unknown ✗ \tilde{\mathcal{O}}(K^{1/3}V_{T}^{1/3}T^{2/3}) \Omega(K^{1/3}V_{T}^{1/3}T^{2/3}) Efroni et al. 2021 Stationary — ✓ \tilde{\mathcal{O}}\left(\frac{K^{1/2}T}{B^{1/2}}\right) \Omega\left(\frac{K^{1/2}T}{B^{1/2}}\right) This Work Non-Stationary Unknown ✓ \tilde{\mathcal{O}}\left(\frac{K^{1/3}V_{T}^{1/3}T}{B^{1/3}}\right) \Omega\left(\frac{K^{1/3}V_{T}^{1/3}T}{B^{1/3}}\right) Table 1: Comparison with the most closely related works, where T is the time horizon, K is the number of arms, V_{T} denotes the variation budget capturing the degree of non-stationarity, and B is the reward feedback querying constraint. \bullet ConFee-nsMAB Framework. We introduce ConFee-nsMAB , a new framework for nsMAB that incorporates a reward feedback querying constraint, limiting the total number of reward feedback queries the agent can issue over the time horizon while learning in non-stationary environments. \bullet Near-Optimal HyQue Algorithm. A standard approach in nsMAB is to run multiple instances of a base algorithm at varying time scales using randomized scheduling to detect non-stationarity [ 37 ] . We extend this multi-scale idea to ConFee-nsMAB , but the extension presents two key challenges: \vartriangleright Query Allocation Trade-off: Naively querying every round quickly exhausts the budget, while querying too infrequently risks missing abrupt changes. Thus, the challenge is to design a query allocation strategy that balances timely detection with budget preservation, including careful distribution across time scales. \vartriangleright Long Non-Query Segments: Longer instances aimed at capturing gradual shifts may contain extended non-query periods, limiting the algorithm’s responsiveness. It is critical to ensure sufficient query frequency for timely change detection without prematurely exhausting the budget. To address these challenges, we propose HyQue , a hybrid query allocation algorithm that combines baseline allocation—ensuring a minimum query rate within each block—with an on-demand mechanism that dynamically injects queries when usage falls behind a near-linear pace. HyQue is prior-free and provably near-optimal, achieving a regret upper bound that matches the lower bound up to logarithmic factors. We establish this lower bound to understand how the reward feedback querying constraint impacts the best-achievable dynamic regret in ConFee-nsMAB . 2 Model and Problem Formulation nsMAB . We consider a nsMAB setting with [K]=\{1,\ldots,K\} arms, where an agent selects one arm k\in[K] at each round t\in[T]=\{1,\dots,T\} . When arm k is pulled, a reward R_{t}^{k}\in[0,1] is obtained, where R_{t}^{k} is a random variable drawn independently from an unknown distribution. Let \mu_{t}^{k} denote the expected reward of arm k at round t . Let \mu:=\{\mu_{t}^{k},k\in[K],t\in[T]\} denote the underlying sequence of true expected rewards for all arms over the time horizon T. In nsMAB , \mu_{t}^{k} may vary across rounds.

Read the complete text