In the standard model of online learning, an agent makes a decision, observes the outcome, and uses that feedback to improve its next move. This cycle assumes that feedback is "free" and instantaneous. However, in many real-world systems—from distributed sensors with limited battery to high-frequency trading platforms with bandwidth caps—observing the results of an action is a costly resource.
Recent research has focused on quantifying the exact mathematical "price" of this limited information. By treating feedback as a constrained budget rather than a guarantee, researchers are uncovering the fundamental trade-offs between communication, memory, and the ability to learn.
The Bandwidth Sample Trade-off
If you restrict the amount of information an algorithm can receive from its environment, you inevitably slow down its learning process. Ohad Shamir established in Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation that there is an unavoidable information-theoretic limit to this relationship.
The intuition is that feedback acts as a "bandwidth" channel. If an agent only receives a few bits of feedback per iteration, it effectively sees a low-resolution version of the world. To compensate for this lack of clarity, the agent needs more data points to reach the same level of accuracy. Shamir proved that the regret (the gap between the agent's performance and the optimal strategy) scales inversely with the square root of the feedback bits. In short: if you cut your feedback in half, you don't just lose a bit of performance; you significantly increase the number of samples required to learn the underlying pattern.
Budgeting for Non-Stationary Worlds
The challenge of limited feedback becomes even more acute when the environment is changing. In a "non-stationary" world, old information quickly becomes obsolete. If an agent has a limited "query budget"—meaning it can only afford to check the true state of the world a few times—it faces a difficult timing problem: when is the most valuable time to ask for feedback?
In Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits, Shaoang Li and Jian Li show that the performance limit in these scenarios is proportional to the cube root of the ratio between total time ($T$) and the query budget ($B$). This $\sqrt[3]{T/B}$ relationship represents a fundamental balance. If the agent queries too often early on, it runs out of budget and becomes "blind" to later changes in the environment. If it queries too slowly, it reacts too late to shifts. The cube root bound defines the optimal "heartbeat" for an agent trying to stay synchronized with a shifting world under a strict information budget.
The Penalty of Partial Observation
Even when the environment is stable, the type of feedback matters as much as the amount. In many resource-constrained problems (often modeled as "Knapsack" problems), an agent might only see the reward for the specific action it took, rather than seeing what would have happened if it had chosen differently.
Zhaohua Chen, Rui Ai, and Mingwei Yang explored this in Contextual Decision-Making with Knapsacks Beyond the Worst Case. They found that moving from "full-information" (seeing all possible outcomes) to "partial-information" (only seeing the outcome of the chosen action) fundamentally changes the complexity of the problem.
In their framework, this shift causes the regret to jump from a constant value to a logarithmic scale. While a logarithmic penalty is relatively small in the long run, it represents the "exploration tax" that must be paid when an agent is forced to learn through trial and error rather than through comprehensive observation. This research suggests that the structure of the feedback—not just its quantity—dictates whether an algorithm can achieve near-perfect performance or is destined to keep making small, unavoidable errors.