Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items

Dimitris Fotakis; Laurent Gourvès; Aris Pagourtzis; Panagiotis Patsilinakos

cs.DSOct 29, 2026

Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items

Authors: Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis, Panagiotis Patsilinakos

Organizations: National Technical University of Athens, Greece · Archimedes, Athena Research Center, Greece · Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, Paris, France

Abstract

In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size of accepted items. When decisions are irrevocable, no algorithm achieves a non-trivial competitive ratio. An essential relaxation that circumvents this impossibility is to allow previously accepted items to be removed from the knapsack (a.k.a. removal). In this work, we investigate possible further improvements on the competitive ratio with removal by bringing together two other previously proposed model extensions: knowledge of an upper bound on the item sizes (a.k.a. bound awareness) and ability to reinsert previously rejected items(a.k.a.recourse). Our contributions are twofold. First, we establish close upper and lower bounds on the competitive ratio under bound awareness, removal and recourse. We show that significant improvements on the best known competitive ratio are possible when the upper bound on the item sizes is not too restrictive and only few uses of recourse are available. Second, we introduce the notion of adaptive online algorithms which do not require to know any upper bound on the item sizes but still achieve performance guarantees comparable to the ones obtained under the bound awareness model.

Figures & tables

Panel of Figure 1 — Figure 1: Bounds on the cr as a function of $u$ . The solid curve depicts $\rho(u)$ , the cr of the bound aware algorithm of [ 12 ] . Bullets and triangles correspond to lower and upper bounds on the optimal cr when recourse is allowed (only drawn for a small number of recourse operations). The maximum number of recourse operations is indicated in parentheses. On the left are the cr s from [ 17 , 7 ] , which are independent of $u$ .

#1	2 medium items	possibly $<3/4$	always $\leq 1$
#2	1 medium item + 1 large item	possibly $<3/4$	always $\leq 1$
#3	1 medium item + 1 extra large item	always $\geq 3/4$	always $\leq 1$
#4	2 large items	always $\geq 3/4$	always $\leq 1$
#5	3 medium items	always $\geq 3/4$	possibly $>1$
#6	1 large item + 1 extra large item	always $\geq 3/4$	possibly $>1$
#7	2 extra large items	always $\geq 3/4$	possibly $>1$

Table 1: Eight combinations of non-small items and comments on their total value. For example, “always

\geq 3/4

” means that the total value of the corresponding combination is always above

3/4

, whereas “possibly

>1

” indicates that the total value may exceed 1.

composition of $S_{i-1}^{\ell}$	$o_{i}$ is extra-large	$o_{i}$ is large	$o_{i}$ is medium
1 extra-large item	case $1$	case $2$	case $3$
1 large item	case $4$	case $5$	case $6$
2 medium items	case $7$	case $8$	case $9$
1 medium and 1 large items	case $10$	case $11$	case $12$

Table 2: All the possible cases at line 20 .

Panel of Figure 2 — Figure 2: The black continuous lines represent the cr of NonAdaptive , the red dashed the cr of Adaptive and the blue dotted the cr of AdaptiveWithRecourse .

Panel of Figure 3 — Figure 3: Lower (solid) and upper (dotted) bounds on the competitive ratio $\rho$ as a function of $u$ .

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 386 papers

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints
Aug 11, 2026Zhen XuContextual Bandits UCB Algorithms
Management School, University of Liverpool, Liverpool, United Kingdom
Satisficing Regret Minimization in Bandits with Knapsacks
Oct 29, 2026Qing Feng, Tianyi Ma, Ruihao ZhuRegret Minimization Multi-Armed Bandits
School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University
Online Packet Scheduling with Deadlines and Learning
May 30, 2026Gianmarco Genalti, Achraf Azize, Vianney PerchetCompetitive Analysis Multi-Armed Bandits
Politecnico di Milano · FairPlay Joint Team, CREST, ENSAE, IP Paris · FairPlay Joint Team, CREST, ENSAE, IP Paris, CRITEO AI Team

Aug 11, 2026J/K move · Enter open · S save

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

Zhen Xu

Management School, University of Liverpool, Liverpool, United Kingdom

Contextual Bandits UCB Algorithms Linear Contextual Bandits

Open paper AskPDF arXiv

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.

Abstract

Combinatorial Optimization

Explore similar work

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

Satisficing Regret Minimization in Bandits with Knapsacks

Online Packet Scheduling with Deadlines and Learning