Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy

• URL: http://arxiv.org/abs/2501.10290v2
• Date: Mon, 10 Mar 2025 18:55:40 GMT
• Title: Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy
• Abstract summary: Multi-armed bandits (MAB) are commonly used in sequential online decision-making.<n>We introduce the Pairwise-Elimination (PE) algorithm for the known reference arm variant and generalize PE to PE-CS for the subsidized best reward variant.<n>Our instance-dependent analysis of PE and PE-CS reveals that both algorithms have an order-wise logarithmic upper bound on Cost and Quality Regret.
• Score: 11.389019661082415
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-armed bandits (MAB) are commonly used in sequential online decision-making when the reward of each decision is an unknown random variable. In practice however, the typical goal of maximizing total reward may be less important than minimizing the total cost of the decisions taken, subject to a reward constraint. For example, we may seek to make decisions that have at least the reward of a reference ``default'' decision, with as low a cost as possible. This problem was recently introduced in the Multi-Armed Bandits with Cost Subsidy (MAB-CS) framework. MAB-CS is broadly applicable to problem domains where a primary metric (cost) is constrained by a secondary metric (reward), and the rewards are unknown. In our work, we address variants of MAB-CS including ones with reward constrained by the reward of a known reference arm or by the subsidized best reward. We introduce the Pairwise-Elimination (PE) algorithm for the known reference arm variant and generalize PE to PE-CS for the subsidized best reward variant. Our instance-dependent analysis of PE and PE-CS reveals that both algorithms have an order-wise logarithmic upper bound on Cost and Quality Regret, making our policies the first with such a guarantee. Moreover, by comparing our upper and lower bound results we establish that PE is order-optimal for all known reference arm problem instances. Finally, experiments are conducted using the MovieLens 25M and Goodreads datasets for both PE and PE-CS revealing the effectiveness of PE and the superior balance between performance and reliability offered by PE-CS compared to baselines from the literature.

Related papers

• Robust Peak-cost Constrained Reinforcement Learning [10.897248153175935]
  We study robust peak-cost constrained reinforcement learning (RP-CRL)<n>The objective is to maximize expected reward while controlling the maximum cost encountered along a trajectory.<n>We show that, unlike standard CMDPs, peak-cost constrained MDPs may not admit zero duality gap.
  arXiv  Detail & Related papers  (2026-07-16T21:00:50Z)
• Selective Ensemble Based on Preference-Directed Multi-Objective Bandits [90.75513823660775]
  We formalize a sequential decision problem under partially specified linear preferences.<n>We then propose a preference-directed upper confidence bound (PrefUCB) algorithm.<n> Experiments on large pre-trained model selective ensemble tasks and online asset allocation under institutional mandates validate our method.
  arXiv  Detail & Related papers  (2026-06-20T07:52:46Z)
• Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy [17.48220873982007]
  In applications, the goal is to minimize cost subject to a constraint on the minimum permissible reward, an objective captured by multi-armed bandits with cost-subsidy (MAB-CS)<n>We characterize the expected sub-optimal samples required by any policy by proving instance-dependent lower bounds.<n>Then, we propose an algorithm called Cost-Ordered Feasibility (COF) that intelligently combine samples from all arms to gauge the feasibility of a cheap arm.
  arXiv  Detail & Related papers  (2026-05-08T03:07:25Z)
• Balancing Performance and Costs in Best Arm Identification [5.558508644689221]
  We propose a new formalism to minimize the risk functional which explicitly balances the performance of the recommended arm and the cost incurred by learning this arm.<n>In this framework, a cost is incurred for each observation during the sampling phase, and upon recommending an arm, a performance penalty is incurred for identifying a suboptimal arm.<n>We derive theoretical lower bounds for the risk of each of two choices for the performance penalty, the probability of misidentification and the simple regret, and propose an algorithm called DBCARE to match these lower bounds up to polylog factors on nearly all problem instances.
  arXiv  Detail & Related papers  (2025-05-26T23:33:43Z)
• Principal-Agent Reward Shaping in MDPs [50.914110302917756]
  Principal-agent problems arise when one party acts on behalf of another, leading to conflicts of interest. We study a two-player Stack game where the principal and the agent have different reward functions, and the agent chooses an MDP policy for both players. Our results establish trees and deterministic decision processes with a finite horizon.
  arXiv  Detail & Related papers  (2023-12-30T18:30:44Z)
• 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)
• Bandits with Replenishable Knapsacks: the Best of both Worlds [26.786438972889208]
  We study a natural generalization of the BwK framework which allows non-monotonic resource utilization. Under an input model, our algorithm yields an instance-independent $tildeO(T1/2)$ regret bound.
  arXiv  Detail & Related papers  (2023-06-14T12:34:00Z)
• Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
  We study the Budgeted Multi-Armed Bandit (MAB) problem, where a player chooses from $K$ arms with unknown expected rewards and costs. We propose a new upper confidence bound (UCB) sampling policy, $omega$-UCB, that uses asymmetric confidence intervals. These intervals scale with the distance between the sample mean and the bounds of a random variable, yielding a more accurate and tight estimation of the reward-cost ratio.
  arXiv  Detail & Related papers  (2023-06-12T12:35:16Z)
• Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards [12.809396600279479]
  We study the problem of Markov decision processes (MDPs) with heavy-tailed rewards under the constraint of differential privacy (DP) By resorting to robust mean estimators for rewards, we first propose two frameworks for heavy-tailed MDPs. We show that there are fundamental differences between the problem of private RL with sub-Gaussian and that with heavy-tailed rewards.
  arXiv  Detail & Related papers  (2023-06-01T20:18:39Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  We study the semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we propose a BCUCB-T algorithm with variance-aware confidence intervals. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition.
  arXiv  Detail & Related papers  (2022-08-31T13:09:39Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  Thompson sampling and other sequential decision-making algorithms are popular approaches to tackle explore/exploit trade-offs in contextual bandits. We show that performance degrades gracefully with misspecified priors.
  arXiv  Detail & Related papers  (2021-07-03T23:17:26Z)
• Output-Weighted Sampling for Multi-Armed Bandits with Extreme Payoffs [11.1546439770774]
  We present a new type of acquisition functions for online decision making in bandit problems with extreme payoffs. We formulate a novel type of upper confidence bound (UCB) acquisition function that guides exploration towards the bandits that are deemed most relevant.
  arXiv  Detail & Related papers  (2021-02-19T18:36:03Z)
• Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
  We formalize decision-making problems with querying budget. We consider multi-armed bandits, linear bandits, and reinforcement learning problems. We show that CBM based algorithms perform well in the presence of adversity.
  arXiv  Detail & Related papers  (2021-02-05T19:56:31Z)
• A One-Size-Fits-All Solution to Conservative Bandit Problems [32.907883501286]
  We study a family of conservative bandit problems (CBPs) with sample-path reward constraints. We propose a One-Size-Fits-All solution to CBPs and present its applications to three encompassed problems.
  arXiv  Detail & Related papers  (2020-12-14T08:50:23Z)

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.