Canonical multi-axis taxonomy
Reader-facing taxonomy for BanditRLlib. It separates mathematical settings, objectives, algorithm families, cross-cutting guarantee properties, RL/application bridges, and unresolved aliases. Classification is distinct from the Bound & Source Atlas and from Frontier open problems.
BAI and regret minimization are objectives; Thompson sampling and GP-UCB are methods; LLM is an application bridge. A result becomes comparable only after the environment/action class, feedback, objective, probability mode, parameters, computation/oracle assumptions and theorem source are fixed.
P0 · objective · case-covered
Pure exploration, fixed-confidence or fixed-budget, with sample complexity/error probability rather than cumulative regret.
Aliases. BAI, Best-1-Arm
Technique map. Elimination / sequential testing
P0 · cross-cutting · missing-topic
Adapt to the best model/algorithm class without knowing its complexity in advance.
Aliases. Model Selection
Technique map. Exponential weights / FTRL / mirror descent · Corralling / model-selection meta-learning
P0 · setting · family-covered
Finite-action bandit baseline; should be the root from which stochastic/adversarial and structured variants branch.
Aliases. MAB
Technique map. Confidence sets → optimism → regret · Posterior sampling / probability matching
P0 · objective · family-covered
Cumulative learning objective; keep separate from pure exploration/identification.
Aliases. RM, regret
P1 · objective · mentioned-not-indexed
Vector rewards, scalarization or Pareto criteria; should not be hidden under single-objective MAB.
Technique map. Scalarization / Pareto / multi-objective selection
P1 · objective · missing-topic
Scalar reward/regret objective; useful mainly as the parent contrast for multi-objective/Pareto bandits.
Aliases. Single-Objective
Technique map. Scalarization / Pareto / multi-objective selection
P1 · objective · missing-topic
Identify/classify arms relative to a threshold; distinct from BAI despite sharing pure-exploration tools.
Aliases. Threshold Bandits
Technique map. Elimination / sequential testing
P1 · objective · missing-topic
Identify a subset or combinatorial optimum; important bridge between BAI and structured bandits.
Technique map. Elimination / sequential testing
P0 · setting · family-covered
Adversarial loss/reward sequence with bandit feedback; a core setting missing as an explicit topic card.
Technique map. Second-order / empirical-Bernstein control · Exponential weights / FTRL / mirror descent
P0 · setting · topic-covered
Finite-moment rather than sub-Gaussian rewards; robust estimation and unknown-tail adaptation are central.
Aliases. heavy-tailed
Technique map. Robust estimation / truncation / robust confidence
P0 · setting · missing-topic
General feedback maps subsuming full information and bandits; important for locating feedback-complexity boundaries.
Technique map. Feedback-graph / partial-monitoring information structure
P0 · setting · case-covered
Algorithms adapt across stochastic/self-bounding/adversarial regimes; corruption is related but not identical.
Aliases. Semi-adversary, BoBW
Technique map. Second-order / empirical-Bernstein control · Exponential weights / FTRL / mirror descent · Corralling / model-selection meta-learning
P0 · setting · family-covered
Stationary stochastic rewards; parent of many finite-arm and structured stochastic settings.
Technique map. Confidence sets → optimism → regret
P1 · setting · topic-covered
Rewards/observations can be corrupted under an explicit adversary and corruption budget.
Technique map. Robust estimation / truncation / robust confidence
P1 · setting · missing-topic
Pairwise/comparative feedback rather than scalar reward observations.
Aliases. Dueling bandits, preference bandits
Technique map. Pairwise preference / dueling reductions
P1 · setting · missing-topic
Selected rewards may be unobserved or censored; missingness mechanism must be part of the model contract.
Aliases. Missing Outcome Bandits, censored bandits
Technique map. Robust estimation / truncation / robust confidence
P1 · objective · missing-topic
Optimize tail risk, safety probability, ruin/survival or other distributional criteria beyond expected reward.
Aliases. risk-aware bandits
Technique map. Primal–dual / Lagrangian resource control
P1 · cross-cutting · topic-covered
Guarantees adapt to variance or second-order quantities rather than only range/sub-Gaussian proxies.
Aliases. Variance-aware Bandits
Technique map. Confidence sets → optimism → regret · Robust estimation / truncation / robust confidence · Second-order / empirical-Bernstein control
P0 · setting · missing-topic
Bandit feedback for convex losses over convex action domains; now mature enough for a dedicated extended route.
Aliases. Convex Bandits, BCO
Technique map. Bandit convex smoothing / gradient estimation
P0 · setting · topic-covered
Combinatorial action sets, often with semi-bandit/full-bandit feedback; oracle/relaxation and computational hardness must be tracked.
Aliases. Combinatorial Bandits
Technique map. Combinatorial oracle / relaxation / semi-bandit estimation
P0 · setting · family-covered
Actions are chosen conditional on observed contexts; realizability and policy/function classes must be explicit.
Aliases. Contextual Bandits
Technique map. Posterior sampling / probability matching
P0 · setting · missing-topic
Known link function applied to a linear predictor; assumptions on link derivatives and contexts matter.
Aliases. GLB
Technique map. Confidence sets → optimism → regret · Low-dimensional / sparse / factorized structure
P0 · setting · missing-topic
Nonparametric function class in an RKHS; information gain and online confidence are core quantities.
Aliases. kernelized bandits
Technique map. Confidence sets → optimism → regret · Posterior sampling / probability matching · RKHS confidence / information gain
P0 · setting · chapter-covered
Mean reward is linear in action/context features; OFUL/self-normalized confidence is a canonical route.
Aliases. stochastic linear bandits
Technique map. Confidence sets → optimism → regret · Posterior sampling / probability matching · Low-dimensional / sparse / factorized structure
P0 · setting · topic-covered
Metric action spaces with Lipschitz reward structure; zooming/near-optimality dimension is a major proof route.
Aliases. Lipschitz Bandits, zooming
Technique map. Zooming / metric localization
P1 · setting · topic-covered
Actions/interventions interact with a causal model and possibly observational data.
Aliases. Causal Bandits
Technique map. Causal intervention / observational transfer
P1 · setting · missing-topic
Reward/action model factorizes across components; distinguish from generic combinatorial and low-rank models.
Aliases. Factored Bandits
Technique map. Low-dimensional / sparse / factorized structure
P1 · setting · missing-topic
Feedback or reward structure is governed by a graph; distinguish feedback graphs from graph-structured reward models.
Aliases. Graphical Bandits, graph feedback
Technique map. Feedback-graph / partial-monitoring information structure
P1 · setting · missing-topic
Structured combinatorial actions defined by matchings; feedback and centralized/decentralized variants should be distinguished.
Aliases. Matching Bandits
Technique map. Combinatorial oracle / relaxation / semi-bandit estimation
P1 · setting · topic-covered
Structured high-dimensional reward parameter; rank, action factorization and observation model must be explicit.
Aliases. Matrix Bandits
Technique map. Low-dimensional / sparse / factorized structure
P1 · setting · missing-topic
If 'multinomial' means MNL choice/assortment bandits, use this canonical label; a generic multinomial reward law is only a reward-distribution specialization.
Aliases. Multinomial Bandits, MNL bandits
Technique map. Low-dimensional / sparse / factorized structure
P1 · setting · missing-topic
Linear/GLM/kernel problems with sparsity or intrinsic-dimension structure; useful cross-pollination route to compressed sensing.
Technique map. Low-dimensional / sparse / factorized structure
P1 · setting · missing-topic
Means obey a unimodal/ordered structure that permits local exploration.
Aliases. Unimodal Bandits
Technique map. Low-dimensional / sparse / factorized structure
P0 · setting · mentioned-not-indexed
Stochastic rewards consume resources; should be an explicit child of constrained/resource bandits.
Aliases. BwK, budgeted bandits
Technique map. Combinatorial oracle / relaxation / semi-bandit estimation · Primal–dual / Lagrangian resource control
P0 · setting · topic-covered
Actions/rewards are subject to resource, feasibility or long-run constraints.
Aliases. Constraints Bandits, Constraint bandits
Technique map. Combinatorial oracle / relaxation / semi-bandit estimation · Primal–dual / Lagrangian resource control
P0 · setting · family-covered
Feedback arrives after delays; distinguish stochastic/adversarial and observable/anonymous delay models.
Technique map. Change detection / windows / variation-budget adaptation
P0 · setting · family-covered
Reward model changes over time; variation, switch, drift and comparator budgets must not be conflated.
Aliases. Dynamic Bandits, nonstationary bandits
Technique map. Change detection / windows / variation-budget adaptation
P0 · cross-cutting · missing-topic
Guarantees adapt to unknown horizon, scale, variation, tail or comparator complexity without prior tuning.
Aliases. Parameter-free
Technique map. Exponential weights / FTRL / mirror descent · Change detection / windows / variation-budget adaptation · Corralling / model-selection meta-learning
P1 · setting · missing-topic
The available arm set grows over time; the user's 'Bolling' label is normalized here to Ballooning.
Aliases. Bolling Bandits, Ballooning Bandits, BL-MAB
Technique map. Change detection / windows / variation-budget adaptation
P1 · setting · missing-topic
Feedback is only available between batches or the number of adaptive rounds is constrained.
Technique map. Change detection / windows / variation-budget adaptation
P1 · setting · missing-topic
Queries trade fidelity/cost against information; connect to multi-fidelity Bayesian optimization.
Aliases. Multi-Fidelity
Technique map. Primal–dual / Lagrangian resource control
P1 · setting · missing-topic
Rewards evolve with pulls or time; each subfamily needs its own dynamics contract.
Aliases. restless bandits
Technique map. Change detection / windows / variation-budget adaptation
P1 · setting · missing-topic
Constraint violations themselves must be controlled; safety semantics differ from generic budget constraints.
Aliases. Safe Bandits
Technique map. Primal–dual / Lagrangian resource control
P1 · setting · missing-topic
Only a subset of arms is available each round.
Aliases. sleeping bandits
Technique map. Change detection / windows / variation-budget adaptation
P1 · setting · mentioned-not-indexed
Learning interacts with fairness or strategic agent constraints; link to the economics/agents textbook routes.
Aliases. incentivized exploration
P1 · setting · missing-topic
Distributed/federated clients learn with communication and heterogeneity constraints.
Aliases. Federated Bandits
Technique map. Distributed coordination / communication / collision control
P1 · setting · topic-covered
Multiple learning agents with communication, collision, cooperation or competition contracts.
Aliases. Multi-Agent
Technique map. Distributed coordination / communication / collision control
P1 · setting · missing-topic
Privacy constraints change achievable regret and proof techniques; currently has explicit COLT open-problem history.
Aliases. differentially private bandits, JDP contextual bandits
Technique map. Privacy accounting / randomized perturbation
P2 · setting · missing-topic
Several related bandit tasks/instances are learned jointly; use only with a source-specific transfer/sharing model.
Aliases. Multi-Bandit
Technique map. Corralling / model-selection meta-learning · Distributed coordination / communication / collision control
P0 · method · chapter-covered
Optimization-based adversarial-bandit methods and best-of-both-worlds variants.
Aliases. EXP3, Tsallis-INF
Technique map. Exponential weights / FTRL / mirror descent
P0 · method · topic-and-chapter-covered
Bayesian/posterior-sampling method; keep as method, not setting.
Aliases. Tompson Sampling, Thompson Sample, TS
Technique map. Posterior sampling / probability matching
P0 · method · chapter-covered
Confidence-bound method family crossing stochastic, linear, kernel and RL settings.
Aliases. UCB
P1 · method · missing-topic
Core method family for pure exploration and confidence-based regret algorithms.
Technique map. Elimination / sequential testing
P1 · method · missing-topic
A method for GP/RKHS bandits, not a separate setting; index it under kernel bandits and UCB methods.
Aliases. Gaussian Process UCB, GP-UCB
Technique map. Confidence sets → optimism → regret · RKHS confidence / information gain
P0 · setting · cross-library-route
Bandit models with genuinely quantum access or quantum-valued environments. Keep reward-oracle QMAB/QLB, quantum-state/observable bandits, and quantum contextual models separate; classical bandit theorems do not transfer without an explicit oracle/statistical bridge.
Aliases. Quantum MAB, QMAB, Quantum Linear Bandits, QLB, quantum reward-oracle bandits, quantum-state bandits
Technique map. Quantum mean estimation / quantum testing / quantum design
P0 · setting · missing-topic
Function-approximation RL routes; kernel RL has explicit COLT open-problem history.
Aliases. linear MDP, kernel RL
Technique map. Confidence sets → optimism → regret · RKHS confidence / information gain · Bellman recursion + optimistic bonuses
P0 · application-bridge · family-and-book-covered
Bandit-to-RL bridge; branch into episodic, discounted and average-reward objectives.
Aliases. RL, MDP
Technique map. Confidence sets → optimism → regret · Bellman recursion + optimistic bonuses
P1 · setting · missing-topic
Sequential decision making under costs/safety constraints.
Technique map. Primal–dual / Lagrangian resource control · Bellman recursion + optimistic bonuses
P1 · setting · missing-topic
RL counterpart of multi-agent bandits; cooperative/competitive/game structure must be explicit.
Aliases. MARL
Technique map. Distributed coordination / communication / collision control
P1 · setting · missing-topic
Learn from a fixed dataset; coverage/concentrability replaces online exploration.
Technique map. Coverage / concentrability / pessimism
P1 · setting · missing-topic
MDP with online/adversarial costs or changing environments; do not abbreviate as OMDP without expansion.
Aliases. online MDP
Technique map. Bellman recursion + optimistic bonuses
P1 · setting · missing-topic
Partial observability changes planning and learning complexity.
Aliases. POMDP
Technique map. Belief-state / memory representation
P2 · application-bridge · missing-topic
Application bridge for preference learning, routing, inference-time allocation, evaluation or adaptation; map each paper back to a precise mathematical setting.
Aliases. LLM
Technique map. Preference / routing / allocation reductions for LLM systems
P1 · ambiguous · quarantine
Ambiguous acronym in the literature: it is used for stochastic linear bandits and also safe linear bandits. Preserve the label for discovery, but require a cited source before mapping a contribution to one canonical setting.
Aliases. SLB
P2 · ambiguous · quarantine
Do not canonicalize until a source defines whether this means online MDP, observable MDP, or another model.
Aliases. OMDP
P2 · ambiguous · quarantine
No stable canonical bandit setting was identified from the bare label; retain as an alias quarantine entry until a paper/source is supplied.
Aliases. Transform
Adding a setting name is not enough. A substantive update must use the repository contribution contract, connect the affected reader/route/progress surfaces, and classify its Lean Graph and Functor Hypergraph delta.