Making sequential decisions is challenging when you only receive partial feedback about the choices you make. This challenge is compounded when there is a penalty for changing your mind. The NeurIPS 2019 paper, "Bandits with Feedback Graphs and Switching Costs," by Raman Arora, Teodor V. Marinov, and Mehryar Mohri, provides a significant theoretical advancement in online learning by addressing these exact constraints.
The authors present new algorithms for the multi-armed bandit problem that incorporate both feedback graphs (side information) and switching costs. By shifting the mathematical focus from a graph's "independence number" to its "domination number," they achieve significantly tighter regret bounds. Ultimately, they prove that side information is far more valuable than previously thought when switching actions is expensive.
The Problem: Partial Feedback and Expensive Switches
In the classic Multi-Armed Bandit (MAB) problem, a learner chooses an action and only observes the loss for that specific action. However, real-world scenarios are often more complex and feature two distinct challenges:
- Feedback Graphs: Choosing one action might reveal information about others. For example, testing a drug on one patient might provide data relevant to patients with similar genetic profiles. This relationship is modeled as a graph, where an edge between two actions means that observing one reveals the loss of the other.
- Switching Costs: In many practical systems, changing actions isn't free. A bank changing its credit card marketing campaign or a factory retooling a machine incurs a tangible "switching cost."
Previous research showed that with switching costs, the "regret"—the difference between the learner's performance and the best possible fixed action—scales with the graph's independence number, denoted as $\alpha(G)$. The authors of this paper identified a critical gap: the independence number is an overly pessimistic measure. They sought to determine if a smaller graph property, the domination number $\gamma(G)$, could provide a tighter, more accurate bound.
Algorithmic Innovations
To tackle this, the authors introduce two primary algorithmic frameworks:
- Adaptive Mini-batching: To handle switching costs, the learner shouldn't change actions every round. Instead, actions are played in "batches." The novelty here is that the batch size is adaptive. Actions that are "revealing" (connected to many others in the feedback graph) are played in larger batches because they provide more information per switch. The algorithm uses a greedy set cover to find a "dominating set"—a small group of actions that can "see" the entire graph.
- Corralling Star-Graphs: This alternative approach decomposes a complex feedback graph into simpler "star graphs" (one central node connected to many leaves). It then uses a meta-algorithm to "corral" these different star-graph experts. While elegant, the authors note this approach currently yields slightly worse theoretical bounds than their adaptive mini-batching method.
- Policy Regret: The authors also extend their work to "adaptive adversaries"—environments that react to the learner's past moves—using the concept of policy regret and counterfactual feedback.
Key Insights and Theoretical Results
As a theoretical machine learning paper, the evaluation relies on rigorous mathematical proofs and the analysis of synthetic graph structures rather than standard empirical datasets.
Domination is Key
The most important insight of the paper is that for environments with switching costs, the domination number $\gamma(G)$ is the correct metric, not the independence number.
Consider a star graph. The independence number $\alpha(G)$ is large (all the leaf nodes), but the domination number $\gamma(G)$ is just 1 (the central node, which observes all leaves). Because $\gamma(G)$ can be exponentially smaller than $\alpha(G)$ in dense graphs, this shift in perspective represents a massive improvement in guaranteed performance. The paper suggests that if switching to a specific action provides a "global view" of the losses of many other actions, the learner can afford to stay with that action longer, amortizing the switching cost more effectively.
Improved Regret Bounds
The authors' best algorithm achieves a pseudo-regret of $\tilde{O}(\gamma(G)^{1/3} T^{2/3})$. This is a significant improvement over the previous state-of-the-art, which was bounded by $\tilde{O}(\alpha(G)^{1/3} T^{2/3})$.
Furthermore, they prove that for certain classes of graphs (like disjoint unions of stars), this $T^{2/3}$ scaling is the best any algorithm can possibly achieve, making their result mathematically "tight." For adaptive environments with memory $m$, they achieve a policy regret bound of $\tilde{O}((m\gamma(G))^{1/3} T^{2/3})$.
Limitations and Future Work
While the paper makes significant strides, several open challenges remain:
- Algorithm Suboptimality: The "Corralling" method currently has a worse dependency on the graph size than the direct adaptive mini-batching approach, which may be an artifact of current analysis techniques rather than a fundamental flaw.
- General Lower Bounds: The authors provide matching lower bounds for specific graph families, but establishing a universal lower bound that holds for any arbitrary graph remains an open theoretical challenge.
- Knowledge of Adversary Memory: The policy regret algorithm requires the learner to know (or have an upper bound on) the adversary's memory $m$, which might not always be available in practical, real-world deployments.
Summary updated