candidate · family:optimism-confidence-regret
Confidence set → optimism → regret
Mechanism. Turn statistical uncertainty into an optimistic upper value, then charge regret to the width/bonus accumulated along the realized trajectory.
Formula/skeleton. good confidence event + optimistic selector => instantaneous regret controlled by confidence width; sum widths to obtain cumulative regret
Domains. finite stochastic bandits · linear bandits · finite-horizon RL
Hypothesis and conclusion map
Hypotheses
- finite-arm concentration ↔ self-normalized linear confidence ↔ value-function confidence/bonus
Conclusions
- arm-count regret ↔ elliptical-potential regret ↔ episodic Bellman-bonus regret
Technique Map. confidence-optimism · rl-bellman-optimism
Candidate Lean substrates. BanditRLProof.UCB · BanditRLProof.OFUL · BanditRLProof.FiniteHorizonRL
Source/route IDs. teaching:ucb · teaching:oful · teaching:finite-horizon-rl
Failure boundary. The confidence objects, dependence structure, planning operator, and width summation are not interchangeable; no generic theorem currently transports all three routes.
candidate · family:information-change-of-measure
Alternative environment → information budget → lower bound
Mechanism. Construct a confusing alternative and convert indistinguishability into regret or sample-complexity cost.
Formula/skeleton. history KL = expected sampling allocation × local KL; testing/change-of-measure forces enough information to distinguish alternatives
Domains. finite-arm minimax lower bounds · instance-dependent bandit lower bounds · best-arm identification
Hypothesis and conclusion map
Hypotheses
- same-policy history law ↔ adaptive stopping/recommendation law
Conclusions
- regret lower bound ↔ pull-count constraint ↔ BAI characteristic/sample complexity
Technique Map. elimination-testing
Candidate Lean substrates. BanditRLProof.LowerBounds
Source/route IDs. textbook:chapter-14 · textbook:chapter-15 · textbook:chapter-16 · banditrlwiki:fixed-confidence-best-arm-identification
Failure boundary. Stopped experiments, permutation-averaged benchmarks, alternative sets, and divergences require additional measurable/stopping interfaces; conceptual overlap is not a local BAI proof.
candidate · family:regularized-potential-stability
Regularized potential → one-step stability → regret
Mechanism. Use a convex/entropy-like potential to telescope learning dynamics while controlling estimator bias and variance.
Formula/skeleton. potential increment + unbiased/controlled estimator + regularizer stability => comparator regret bound
Domains. EXP3/exponential weights · Tsallis-FTRL · online learning
Hypothesis and conclusion map
Hypotheses
- Shannon/exponential potential ↔ Tsallis regularizer
Conclusions
- adversarial expected/high-probability regret ↔ best-of-both-worlds/second-order regret
Technique Map. exponential-weights-ftrl · bandit-convex-smoothing
Candidate Lean substrates. BanditRLProof.Exp3 · BanditRLProof.Tsallis
Source/route IDs. teaching:exp3 · teaching:tsallis
Failure boundary. Different regularizers and estimators have different domains, exploration requirements, and stability inequalities; there is no certified generic FTRL transport theorem in BanditRLlib.
candidate · family:posterior-randomization
Posterior law → probability matching → Bayesian regret
Mechanism. Replace explicit optimism by randomized action selection induced by posterior uncertainty, then control regret through confidence/information structure.
Formula/skeleton. posterior sample / posterior-optimal action law = posterior probability that an action is optimal
Domains. Thompson sampling · Bayesian decision processes
Hypothesis and conclusion map
Hypotheses
- finite-arm stationary posterior kernel ↔ richer posterior-sampling models
Conclusions
- probability matching ↔ Bayesian regret decomposition
Technique Map. posterior-probability-matching
Candidate Lean substrates. BanditRLProof.Thompson
Source/route IDs. teaching:thompson
Failure boundary. The compiled route is stationary finite-arm; contextual, linear, nonstationary, and posterior-sampling RL need additional model-specific semantics.
candidate · family:robust-confidence
Robust estimator → confidence object → regret
Mechanism. Factor the proof into an estimator-specific concentration layer and a decision layer that consumes only a confidence contract.
Formula/skeleton. replace fragile empirical mean by robust/variance-aware/private estimate; prove valid confidence; reuse decision analysis with a changed uncertainty radius
Domains. heavy-tailed bandits · corruption-tolerant bandits · missing/censored outcomes · variance-aware bandits · private bandits
Hypothesis and conclusion map
Hypotheses
- finite moments / corruption budget / censoring model / empirical variance / privacy semantics → confidence validity and radius
Conclusions
- robust UCB/elimination regret ↔ corruption/variance/privacy-adaptive regret
Technique Map. robust-estimation · second-order-empirical-bernstein · privacy-randomization
Candidate Lean substrates. BanditRLProof.Concentration · BanditRLProof.UCB
Source/route IDs. setting:heavy-tailed · setting:corruption-tolerant · setting:missing-outcome · setting:variance-aware · setting:privacy
Failure boundary. The estimators are not interchangeable: contamination, missingness, tail moments, and differential privacy require different probability spaces and bias terms. No generic robust-confidence interface is compiled yet.
candidate · family:metric-localization
Metric/RKHS geometry → localized uncertainty → regret
Mechanism. Replace raw arm count or ambient dimension by a geometry-sensitive complexity such as covering/zooming dimension or information gain.
Formula/skeleton. global action space → local complexity/effective dimension around plausible near-optimal functions/actions → confidence-driven exploration
Domains. Lipschitz/continuum bandits · kernel/RKHS bandits · GP-UCB · kernel RL
Hypothesis and conclusion map
Hypotheses
- metric Lipschitz structure ↔ RKHS norm/kernel posterior geometry
Conclusions
- zooming regret ↔ GP/RKHS confidence/information-gain regret
Technique Map. zooming-metric-localization · rkhs-information-gain
Candidate Lean substrates. No local substrate mapped yet.
Source/route IDs. setting:lipschitz · setting:kernel-bandits · setting:gp-ucb · setting:linear-kernel-mdp
Failure boundary. Zooming dimension and RKHS information gain are different complexity objects; this family records the localization skeleton, not an equivalence between their bounds.
candidate · family:oracle-relaxation
Hard action set / resource constraint → oracle or relaxation → learnable surrogate
Mechanism. Separate statistical uncertainty from the combinatorial or constrained optimization subproblem and expose approximation/oracle assumptions explicitly.
Formula/skeleton. statistical estimate + optimization oracle/relaxation/dual variable → feasible or approximately optimal action → regret plus computational/resource error
Domains. combinatorial bandits · matching bandits · Bandits with Knapsacks · constrained/safe bandits
Hypothesis and conclusion map
Hypotheses
- combinatorial oracle / LP relaxation / dual feasibility / budget semantics
Conclusions
- regret ↔ oracle approximation + statistical error + resource/safety violation
Technique Map. combinatorial-oracle-relaxation · primal-dual-resource-control
Candidate Lean substrates. No local substrate mapped yet.
Source/route IDs. setting:combinatorial · setting:matching · setting:bandits-with-knapsacks · setting:constrained · setting:safe-bandits
Failure boundary. NP-hard optimization, semi-bandit feedback, stochastic resource consumption and hard safety constraints induce different approximation and feasibility contracts.
candidate · family:structured-dimension
Ambient model → intrinsic structure → lower-dimensional confidence
Mechanism. Compress the learning problem to a lower-complexity parameter or local structure before applying confidence/testing machinery.
Formula/skeleton. identify structural parameterization + prove estimator/confidence in intrinsic coordinates + explore according to intrinsic complexity
Domains. linear/GLM bandits · sparse bandits · matrix/low-rank bandits · factored bandits · unimodal bandits · MNL/assortment bandits
Hypothesis and conclusion map
Hypotheses
- linearity / sparsity / low rank / factorization / order / likelihood structure
Conclusions
- ambient-size dependence → intrinsic dimension/rank/sparsity/graph/parameter dependence
Technique Map. structured-low-dimensionality
Candidate Lean substrates. BanditRLProof.OFUL
Source/route IDs. setting:linear · setting:generalized-linear · setting:matrix-low-rank · setting:sparse-high-dimensional · setting:factored · setting:unimodal · setting:mnl
Failure boundary. Sparsity, rank, factorization, unimodality and parametric likelihoods are not mutually reducible; each needs its own identifiability and estimator interface.
candidate · family:adaptation-meta
Unknown environment complexity → detection/meta-combination → adaptive regret
Mechanism. Move uncertainty from reward parameters to the environment class itself and pay an adaptation overhead instead of assuming the class parameter is known.
Formula/skeleton. run/restart/window/combine base learners + detect or hedge over unknown complexity → regret tracks variation/switches/model complexity without prior tuning
Domains. nonstationary bandits · delayed/availability bandits · parameter-free learning · model selection · best-of-both-worlds
Hypothesis and conclusion map
Hypotheses
- variation/switch/delay/availability/model-class budgets
Conclusions
- static regret → dynamic/model-adaptive/parameter-free regret
Technique Map. nonstationary-adaptation · corralling-model-selection
Candidate Lean substrates. BanditRLProof.Exp3 · BanditRLProof.Tsallis
Source/route IDs. setting:dynamic-nonstationary · setting:delayed · setting:parameter-free · setting:model-selection · setting:semi-adversarial
Failure boundary. Restarting, corralling, delay compensation and best-of-both-worlds self-bounding arguments use different observability and overhead mechanisms.
candidate · family:structured-information-transfer
Nonstandard feedback structure → transferable information → effective observations
Mechanism. Exploit the observation graph/causal model/preference relation to transfer evidence across actions.
Formula/skeleton. one chosen action/intervention/comparison reveals structured information about other latent rewards/actions → update a richer information state than the played arm alone
Domains. causal bandits · feedback-graph bandits · partial monitoring · dueling/preference bandits
Hypothesis and conclusion map
Hypotheses
- causal graph / feedback graph / signal map / preference model
Conclusions
- effective sample information → regret/sample complexity
Technique Map. causal-intervention-transfer · graph-feedback-information · preference-comparison
Candidate Lean substrates. No local substrate mapped yet.
Source/route IDs. setting:causal · setting:graphical · setting:partial-monitoring · setting:dueling
Failure boundary. Causal interventions, graph side-observations, partial-monitoring signals and pairwise preferences encode fundamentally different information channels.
candidate · family:distributed-information
Many learners → communication/coordination → pooled or decentralized learning
Mechanism. Trade communication, decentralization, collisions or heterogeneity against the statistical gain from multiple learners.
Formula/skeleton. local observations + communication/collision/game protocol → shared or strategically coupled information state → group regret/sample complexity
Domains. multi-agent bandits · federated bandits · multi-task bandits · multi-agent RL
Hypothesis and conclusion map
Hypotheses
- communication graph / collision model / heterogeneity / cooperation-competition
Conclusions
- single-agent complexity → network/team/system complexity
Technique Map. distributed-coordination
Candidate Lean substrates. No local substrate mapped yet.
Source/route IDs. setting:multi-agent · setting:federated · setting:multi-bandit · setting:multi-agent-rl
Failure boundary. Cooperative pooling, federated heterogeneity, collisions and competitive games have different objectives and cannot share one theorem statement.
candidate · family:objective-transport
Scalar reward objective → alternative objective geometry
Mechanism. Expose the objective transformation before applying algorithms so scalarization, Pareto order, tail risk and safety are not silently conflated.
Formula/skeleton. replace scalar expectation by vector/risk/constraint functional; identify the correct ordering/comparator; then rebuild confidence and regret around that comparator
Domains. single-objective regret · multi-objective/Pareto bandits · risk-sensitive/survival bandits
Hypothesis and conclusion map
Hypotheses
- scalar comparator ↔ Pareto/scalarized/risk/constraint comparator
Conclusions
- ordinary regret ↔ Pareto/risk/constrained performance
Technique Map. multiobjective-scalarization · primal-dual-resource-control
Candidate Lean substrates. No local substrate mapped yet.
Source/route IDs. setting:single-objective · setting:multi-objective · setting:risk-sensitive · setting:constrained
Failure boundary. Different scalarizations and risk measures change the mathematical order itself; no universal objective transport theorem is claimed.
candidate · family:coverage-vs-exploration
Online exploration ↔ offline coverage
Mechanism. Replace the ability to gather new information with an explicit dataset-support condition, often reversing optimism into pessimism.
Formula/skeleton. online visitation generated by exploration ↔ fixed data distribution with coverage/concentrability assumptions
Domains. online bandits/RL · offline RL
Hypothesis and conclusion map
Hypotheses
- exploration policy/occupancy ↔ behavior-data coverage or concentrability
Conclusions
- online regret/sample efficiency ↔ offline value/policy error
Technique Map. offline-coverage-concentrability
Candidate Lean substrates. BanditRLProof.FiniteHorizonRL
Source/route IDs. setting:offline-rl · setting:mdp-rl
Failure boundary. Coverage assumptions are external properties of a fixed dataset and do not follow from online optimism.
candidate · family:representation-lift
Observed interface → richer latent/information representation
Mechanism. Formalize the representation map first, then reuse bandit/RL machinery only after the induced state/feedback/objective contract is proved.
Formula/skeleton. application observation/history → sufficient/belief/task-specific state representation → standard decision-theoretic contract
Domains. POMDPs · LLM system bandit reductions · structured application bridges
Hypothesis and conclusion map
Hypotheses
- partial observation / application telemetry ↔ information state or explicit bandit/RL reduction
Conclusions
- application objective ↔ canonical regret/value/sample-complexity objective
Technique Map. partial-observability-belief · llm-preference-routing
Candidate Lean substrates. BanditRLProof.FiniteHorizonRL
Source/route IDs. setting:pomdp · setting:llm-bandits
Failure boundary. A heuristic reduction is not a theorem: sufficiency, Markov structure, feedback semantics and objective preservation require separate proofs.
candidate · family:quantum-estimation-testing
Quantum oracle access → quantum estimation/testing → new regret scale
Mechanism. Change the information-access primitive itself, then separate quantum query complexity from the classical decision skeleton.
Formula/skeleton. coherent reward/state oracle + quantum mean estimator or quantum hypothesis test → fewer oracle queries per confidence decision; polynomial/testing lower bound certifies the achievable scale
Domains. quantum MAB · quantum linear bandits · quantum-state/observable bandits · classical bandit lower-bound/testing routes
Hypothesis and conclusion map
Hypotheses
- classical samples ↔ unitary reward oracle / state copies / observables; classical testing ↔ quantum query testing
Conclusions
- classical sqrt(T)-type scales ↔ logarithmic/polylogarithmic horizon dependence in specific quantum-oracle models
Technique Map. quantum-estimation-testing
Candidate Lean substrates. BanditRLProof.Concentration · BanditRLProof.OFUL · BanditRLProof.LowerBounds
Source/route IDs. source:wan-et-al-2023-qmab-qlb · source:liu-li-lui-2026-quantum-lower-bounds · source:lumbreras-haapasalo-tomamichel-2022-quantum-state-bandits · external:aspbe
Failure boundary. Quantum reward-oracle, quantum-state/observable and contextual quantum-data models are different. Existing ASPBE and external quantum libraries are reference/circuit/semantic substrates, not imported ABRL proofs; every cross-library reuse needs a toolchain/license/API bridge.