Papers for

dynamic pricing teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Algorithm optimizes rewards with limited resources in decision problems

Satisficing Regret Minimization in Bandits with Knapsacks

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.

Thu 29 OctMachine Learning
The gist
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.
Open → 2610.39321v1