Bandits with Feedback Graphs and Switching Costs

Raman Arora, Teodor V. Marinov, Mehryar Mohri

Abstract

We study the adversarial multi-armed bandit problem where partial observations are available and where, in addition to the loss incurred for each action, a switching cost is incurred for shifting to a new action. All previously known results incur a factor proportional to the independence number of the feedback graph. We give a new algorithm whose regret guarantee depends only on the domination number of the graph. We further supplement that result with a lower bound. Finally, we also give a new algorithm with improved policy regret bounds when partial counterfactual feedback is available.

Introduction

The classic multi-armed bandit (MAB) problem requires a learner to choose an action and observe only the reward or loss for that specific choice. This paper addresses a more complex variant incorporating two real-world constraints: partial observability and switching costs.

Partial observability is modeled via feedback graphs, where an edge between two actions indicates that choosing one reveals information about the other. For instance, testing a specific drug might yield data relevant to chemically similar compounds. Switching costs represent the penalties incurred when changing actions, such as the overhead of retooling a factory line or updating a financial product offering.

The core challenge lies in the exploration-exploitation-switching tradeoff. While exploration is necessary to find optimal actions, it typically requires frequent switching, which is costly. Previous literature suggested that the difficulty of this problem scales with the graph's independence number ($\alpha(G)$). This work demonstrates that for "informed" learners, the complexity actually depends on the domination number ($\gamma(G)$), which can be significantly smaller.

Methods

The authors propose a strategy centered on minimizing switches while maximizing information gain.

Adaptive Mini-batching

To mitigate switching costs, the learner does not change actions every round. Instead, actions are played for "mini-batches" of time. Unlike standard approaches that use fixed batch sizes, this algorithm employs adaptive batching. The duration of a batch depends on the action's informational value. For example, in a star graph, the algorithm prioritizes the central "revealing" node, spending more time there to gather information about the entire neighborhood at a lower switching cost.

A star graph where the central node provides information about all surrounding leaf nodes.

Graph Partitioning via Dominating Sets

For general graph structures, the algorithm computes an approximate minimum dominating set ($R$). It then partitions the graph into disjoint star-like clusters. By focusing exploration on these dominating vertices, the learner can observe the losses of all actions while minimizing the total number of expensive switches.

Key Insights: Domination over Independence

The pivotal realization of this research is that in the presence of switching costs, the ability to observe many nodes from a single point (domination) is more valuable than the number of nodes that are mutually unobservable (independence). If a single action reveals information about 100 others, the learner only pays one switching cost to gain data on 101 actions.

This leads to Information-Directed Batching, where batch sizes are determined by the "revealing" power of an action. Actions in the dominating set are treated as keys to efficient exploration. Additionally, the authors correct a technical inaccuracy in previous literature, providing a new lower bound of $\Omega(T^{2/3})$ for any non-complete feedback graph.

Key Results

  • Improved Regret Bound: The proposed algorithm achieves a pseudo-regret of $\tilde{O}(\gamma(G)^{1/3} T^{2/3})$. Since $\gamma(G) \le \alpha(G)$, this represents a strict improvement over the previous state-of-the-art $\tilde{O}(\alpha(G)^{1/3} T^{2/3})$.
  • Matching Lower Bounds: The authors prove a lower bound of $\Omega(\gamma(G)^{1/3} T^{2/3})$ for specific graph families, establishing the near-optimality of their algorithm regarding both time ($T$) and graph structure ($\gamma(G)$).
  • Policy Regret: The results extend to "policy regret" against adaptive adversaries with memory $m$, achieving a bound of $\tilde{O}((m\gamma(G))^{1/3} T^{2/3})$.

Limitations and Future Work

The current algorithms assume an informed setting, where the feedback graph is known at the start. Extending these optimal $\gamma(G)$ bounds to the uninformed setting, where the graph is revealed incrementally, remains an open challenge. Furthermore, while the lower bound matches for star-graph unions, a universal matching lower bound for all graph families is yet to be proven. Future research could also explore non-uniform or budgeted switching costs.

Summary updated

Abstract

We study the adversarial multi-armed bandit problem where partial observations are available and where, in addition to the loss incurred for each action, a \emph{switching cost} is incurred for shifting to a new action. All previously known results incur a factor proportional to the independence number of the feedback graph. We give a new algorithm whose regret guarantee depends only on the domination number of the graph. We further supplement that result with a lower bound. Finally, we also give a new algorithm with improved policy regret bounds when partial counterfactual feedback is available.
BibTeX
@inproceedings{arora2019bandits,
  author = {Raman Arora and Teodor V. Marinov and Mehryar Mohri},
  title = {{Bandits with Feedback Graphs and Switching Costs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=uQucM-C0fHj},
}
Figure