Summary
Some decisions must be made repeatedly under limited resources, with the goal of getting good enough rewards rather than perfect ones. The authors study how to choose actions so that rewards stay above a desired level as often as possible without running out of resources prematurely. They propose a new method called SELECTwK that uses an existing technique as a tool to find and test actions meeting these goals. Their analysis shows that this method carefully balances reward targets and resource limits, achieving consistently small shortfalls under certain conditions. They also test their approach on problems like pricing items with limited inventory and show it works well in practice.
What this means in practice
- •For dynamic pricing teams: Set prices sequentially to keep average revenue above a target while managing limited inventory effectively using the proposed satisficing algorithm.
- •For online advertising teams: Allocate ad impressions to keep click or conversion rates above satisfactory levels under budget limits using satisficing regret control.
Abstract
We study satisficing regret minimization in bandits with knapsacks (BwK), where a learner sequentially selects randomized policies, i.e., distributions over arms, to obtain mean rewards above a satisficing threshold as frequently as possible while respecting finite resource budgets. The performance is measured by satisficing regret, the cumulative deficits of the selected policies' mean rewards below this threshold. Resource constraints introduce two difficulties: an algorithm can incur linear satisficing regret even with small standard regret as deficits to the threshold cannot be compensated, and random consumption can cause early resource depletion even when policies are feasible in expectation. To address these challenges, we propose SELECTwK, a general algorithmic template that uses a BwK learning oracle algorithm with sub-linear expected (standard) regret upper bound to search for and test candidate satisficing policies (i.e., policies whose mean rewards exceed satisficing threshold and whose expected resource consumption is feasible over the time horizon). Our regret analysis, supported by an LP-duality argument, establishes that SELECTwK attains constant expected satisficing regret when a satisficing policy exists. We further introduce a stronger regret condition that bounds the expected sum of positive reward deficits to the optimal one at each time step, under which SELECTwK achieves a sharper constant bound together with a sub-linear bound in the time horizon. As a complement, SELECTwK still preserves the oracle's sub-linear expected standard regret bound if the satisficing threshold is unattainable. Finally, we establish the oracle conditions and corresponding satisficing regret bound for existing finite-armed BwK and dynamic pricing algorithms, and conduct numerical experiments on dynamic pricing with limited inventory to demonstrate the empirical performance of SELECTwK.