Search papers, labs, and topics across Lattice.
This paper investigates off-policy learning (OPL) in contextual bandits under the constraint of limited item supply, a common scenario in applications like coupon allocation and e-commerce. It demonstrates that standard greedy OPL methods are suboptimal in such settings due to the risk of early item depletion. The authors then introduce Off-Policy learning with Limited Supply (OPLS), which prioritizes items with relatively higher expected rewards compared to other users, leading to more efficient allocation. Empirical results on synthetic and real-world datasets confirm that OPLS outperforms existing OPL methods.
Greedy off-policy learning, optimal in theory, can fail spectacularly when supplies are limited, but a simple fix鈥攑rioritizing items with high *relative* reward鈥攃an restore performance.
We study off-policy learning (OPL) in contextual bandits, which plays a key role in a wide range of real-world applications such as recommendation systems and online advertising. Typical OPL in contextual bandits assumes an unconstrained environment where a policy can select the same item infinitely. However, in many practical applications, including coupon allocation and e-commerce, limited supply constrains items through budget limits on distributed coupons or inventory restrictions on products. In these settings, greedily selecting the item with the highest expected reward for the current user may lead to early depletion of that item, making it unavailable for future users who could potentially generate higher expected rewards. As a result, OPL methods that are optimal in unconstrained settings may become suboptimal in limited supply settings. To address the issue, we provide a theoretical analysis showing that conventional greedy OPL approaches may fail to maximize the policy performance, and demonstrate that policies with superior performance must exist in limited supply settings. Based on this insight, we introduce a novel method called Off-Policy learning with Limited Supply (OPLS). Rather than simply selecting the item with the highest expected reward, OPLS focuses on items with relatively higher expected rewards compared to the other users, enabling more efficient allocation of items with limited supply. Our empirical results on both synthetic and real-world datasets show that OPLS outperforms existing OPL methods in contextual bandit problems with limited supply.
