Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

• URL: http://arxiv.org/abs/2608.11383v1
• Date: Tue, 11 Aug 2026 19:46:10 GMT
• Title: Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints
• Abstract summary: We study new algorithms for Contextual Bandits with Knapsack.<n>We show that by taking advantage of re-optimization, our algorithm achieves an average regret of $O(frac(ln T)3T)$ where $T$ is the horizon length.
• Score: 3.2017121489002744
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of $O(\frac{(\ln T)^3}{T})$ where $T$ is the horizon length. Our bound significantly reduces the $O(\frac{1}{\sqrt{T}})$ bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.

Related papers

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints [8.314956969778692]
  We study an online learning problem with long-term budget constraints in the adversarial setting.<n>In this problem, at each round $t$, a learner selects an action from a convex set, after which an adversary reveals a cost function.<n>Our approach yields an efficient solution for the $textttAdversas$ problem with improved guarantees.
  arXiv  Detail & Related papers  (2025-08-23T11:21:24Z)
• Online Linear Programming with Batching [18.989352151219336]
  We study Online Linear Programming (OLP) withOmega. We show that the ability to delay decisions brings better operational performance, as measured by regret. All the proposed algorithms delay decisions on customers arriving in only the first and the last batch.
  arXiv  Detail & Related papers  (2024-08-01T06:13:24Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation [41.460894569204065]
  We study lifelong reinforcement learning (RL) in a regret setting of linear contextual Markov decision process (MDP) We propose an algorithm, called UCB Lifelong Value Distillation (UCBlvd), that provably achieves sublinear regret for any sequence of tasks.
  arXiv  Detail & Related papers  (2022-06-01T06:53:28Z)
• New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees [21.30065439295409]
  We present new efficient textitprojection-free algorithms for online convex optimization (OCO) Our algorithms are based on the textitonline gradient descent algorithm with a novel and efficient approach to computing so-called textitinfeasible projections We present algorithms which, using overall $O(T)$ calls to the separation oracle, guarantee $O(sqrtT)$ adaptive regret and $O(T3/4)$ adaptive expected regret.
  arXiv  Detail & Related papers  (2022-02-09T20:56:16Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [50.50545326342971]
  We formulate the problem of maximizing a non-linear concave function of multiple long-term objectives.<n>A policy-gradient based model-free algorithm is proposed for the problem.<n>The proposed algorithm is shown to achieve convergence to within an $epsilon$ of the global optima.
  arXiv  Detail & Related papers  (2021-05-28T22:20:54Z)
• A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit [2.9998316151418107]
  We consider a dynamic set optimization problem, where a decision-maker offers a subset of products to a consumer. We model consumer choice behavior using the widely used Multinomial Logit (MNL) model. We show that the regret is bounded by $O(sqrtdT + kappa)$, significantly improving the performance over existing methods.
  arXiv  Detail & Related papers  (2020-11-28T00:20:36Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of ofulq. We show that an $epsilon$-optimistic controller can be computed efficiently by solving at most $Obig(log (1/epsilon)big)$ Riccati equations.
  arXiv  Detail & Related papers  (2020-07-13T16:30:47Z)

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.