Introduction
The field of Multi-Armed Bandits (MAB) has seen a significant surge in research, leading to a "combinatorial explosion" of algorithms and problem formulations. For practitioners at major platforms like Amazon or Netflix, selecting the appropriate bandit flavor—be it contextual, slate, or adversarial—is a daunting task. While textbooks often focus on mathematical rigor and application surveys list success stories, there is a distinct lack of a structured decision-making framework. This paper bridges that gap by providing a "navigation map" that helps engineers align business constraints, such as delayed rewards or complex action structures, with the right algorithmic literature.
Navigating by Reward Properties
The first axis of the proposed framework focuses on the nature of the reward signal. Choosing the right algorithm depends heavily on how "success" is measured and reported.
The authors identify six critical dimensions for reward signals that dictate algorithm choice:
- Scalar vs. Vector: Determines if the optimization is single-objective or multi-objective (e.g., optimizing for both clicks and revenue).
- Distributional Assumption: Distinguishes between stochastic environments (stable over time) and adversarial ones (no probabilistic assumptions).
- Relativity: Contrasts absolute rewards with dueling bandits, where feedback is limited to relative preferences between actions.
- Granularity: Differentiates between aggregated rewards and semi-bandits, which provide feedback on individual components of a complex action.
- Delay: Addresses the reality of bounded vs. indefinite delays, a common challenge in subscription services where conversion may take weeks.
- Value Type: Categorizes rewards as binary (e.g., clicks) or numerical (e.g., total purchase value).
Navigating by Action Properties
The second axis categorizes how actions are structured and the scale of the choice set. Actions are broadly classified into three types: Single (selecting one item), Slate (choosing a ranked list), and Combinatorial (selecting a set of sub-actions simultaneously).
The size of the action set is equally important. As the number of choices grows from dozens to millions, the strategy must shift from simple Arm IDs to feature-based representations to handle the "cold-start" problem and enable generalization across similar items.
For infinite action spaces, such as dynamic pricing or hyperparameter search, continuous action bandits are required. The framework helps map these specific business problems to nodes in the decision tree, providing a "cheat sheet" for researchers to find empirically validated starting points.
Key Results: A Practitioner's Lookup Table
The primary contribution of this work is the mapping of specific business problems to algorithmic references. By identifying the intersection of reward and action properties, practitioners can identify the most relevant literature:
- Optimizing inventory buying: Requires numerical reward bandits (Node 2 in Figure 1).
- Free-trial marketing: Necessitates bandits with delayed feedback (Node 5 in Figure 1).
- Whole-page optimization: Best addressed via combinatorial bandits.
Key Insights and Future Work
The paper highlights that bandits sit in the "middle ground" between supervised learning and full Reinforcement Learning (RL). If an action does not significantly alter the future state of the environment, MABs offer a more efficient alternative to full RL. Furthermore, in large-scale E-commerce, featurizing actions is mandatory to solve the cold-start problem for new inventory.
While the map is not exhaustive and "hybrid" problems (e.g., adversarial slate bandits with delays) remain under-researched, it serves as a robust starting point. Future research is encouraged in areas like Offline Policy Evaluation (OPE) to ensure safer deployments in non-stationary environments and large action sets.
Summary updated