Cascading Bandits With Feedback

• URL: http://arxiv.org/abs/2511.10938v1
• Date: Fri, 14 Nov 2025 03:55:22 GMT
• Title: Cascading Bandits With Feedback
• Abstract summary: We study a variant of the cascade bandit model in which each arm corresponds to an inference model with an associated accuracy and error probability.<n>We analyse four decision-making policies-Explore-then-Commit, Action Elimination, Lower Confidence Bound (LCB), and Thompson Sampling-and provide sharp theoretical regret guarantees for each.
• Score: 4.305007244430146
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Motivated by the challenges of edge inference, we study a variant of the cascade bandit model in which each arm corresponds to an inference model with an associated accuracy and error probability. We analyse four decision-making policies-Explore-then-Commit, Action Elimination, Lower Confidence Bound (LCB), and Thompson Sampling-and provide sharp theoretical regret guarantees for each. Unlike in classical bandit settings, Explore-then-Commit and Action Elimination incur suboptimal regret because they commit to a fixed ordering after the exploration phase, limiting their ability to adapt. In contrast, LCB and Thompson Sampling continuously update their decisions based on observed feedback, achieving constant O(1) regret. Simulations corroborate these theoretical findings, highlighting the crucial role of adaptivity for efficient edge inference under uncertainty.

Related papers

• Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inference [2.9618272039677667]
  We provide the first investigation into adaptive experimental design, focusing on the trade-off between regret and statistical power in multi-armed bandits (CMAB)<n>We propose two algorithms MixCombKL and MixCombUCB respectively for two relevant cases under different information structures.
  arXiv  Detail & Related papers  (2026-02-27T17:58:37Z)
• Latent Chain-of-Thought for Visual Reasoning [53.541579327424046]
  Chain-of-thought (CoT) reasoning is critical for improving the interpretability and reliability of Large Vision-Language Models (LVLMs)<n>We reformulate reasoning in LVLMs as posterior inference and propose a scalable training algorithm based on amortized variational inference.<n>We empirically demonstrate that the proposed method enhances the state-of-the-art LVLMs on seven reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-10-27T23:10:06Z)
• AdvChain: Adversarial Chain-of-Thought Tuning for Robust Safety Alignment of Large Reasoning Models [62.70575022567081]
  We propose AdvChain, an alignment paradigm that teaches models dynamic self-correction through adversarial CoT tuning.<n>Our work establishes a new direction for building more robust and reliable reasoning models.
  arXiv  Detail & Related papers  (2025-09-29T04:27:23Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards [5.347237827669861]
  We study the piecewise stationary semi-bandit problem with causally related rewards. In our nonstationary environment, variations in the base arms' distributions, causal relationships between rewards, or both, change the reward generation process. The problem becomes aggravated in the semi-bandit setting, where the decision-maker only observes the outcome of the selected bundle of arms.
  arXiv  Detail & Related papers  (2023-07-26T12:06:13Z)
• Best of Both Worlds Model Selection [39.211071446838474]
  We study the problem of model selection in bandit scenarios in the presence of nested policy classes. Our approach requires that each base learner comes with a candidate regret bound that may or may not hold. These are the first theoretical results that achieve best of both world (stochastic and adversarial) guarantees while performing model selection in (linear) bandit scenarios.
  arXiv  Detail & Related papers  (2022-06-29T20:57:30Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  We show that the Decision-Estimation Coefficient is necessary and sufficient to obtain low regret for adversarial decision making. We provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures.
  arXiv  Detail & Related papers  (2022-06-27T06:20:37Z)
• Continuous Mean-Covariance Bandits [39.820490484375156]
  We propose a novel Continuous Mean-Covariance Bandit model to take into account option correlation. In CMCB, there is a learner who sequentially chooses weight vectors on given options and observes random feedback according to the decisions. We propose novel algorithms with optimal regrets (within logarithmic factors) and provide matching lower bounds to validate their optimalities.
  arXiv  Detail & Related papers  (2021-02-24T06:37:05Z)
• Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounders [62.54431888432302]
  We study an OPE problem in an infinite-horizon, ergodic Markov decision process with unobserved confounders. We show how, given only a latent variable model for states and actions, policy value can be identified from off-policy data.
  arXiv  Detail & Related papers  (2020-07-27T22:19:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.