Episodic Contextual Bandits with Knapsacks under Conversion Models
Wang Chi Cheung, Zitian Li · 2025
Read Episodic Contextual Bandits with Knapsacks under Conversion Models by Wang Chi Cheung, Zitian Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06859.txt.
Introduction
Wang Chi Cheung and Zitian Li study online choices under tight resource budgets across episodes. Each episode starts with a fresh stock of resources, and the spread of requests shifts within an episode. A hidden conversion model, shared by all episodes, links each request and choice to a random outcome. Uses range from pricing goods that spoil to bids in repeated auctions.
Their algorithm keeps total regret growing slower than the count of episodes. It leans on an oracle that gives confidence bounds with like guarantees. The hard part is the endless range of request types, which blows up the state space. Extra unlabeled feature data can sharpen the bounds in some settings. The frame adds a fresh case to budget bandit theory.
Catalog record
| CREATOR | Wang Chi Cheung, Zitian Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06859
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Episodic Contextual Bandits with Knapsacks under Conversion Models Wang Chi Cheung, Zitian Li Abstract We study an online setting, where a decision maker (DM) interacts with contextual bandit-with-knapsack (BwK) instances in repeated episodes. These episodes start with different resource amounts, and the contexts’ probability distributions are non-stationary in an episode. All episodes share the same latent conversion model, which governs the random outcome contingent upon a request’s context and an allocation decision. Our model captures applications such as dynamic pricing on perishable resources with episodic replenishment, and first price auctions in repeated episodes with different starting budgets. We design an online algorithm that achieves a regret sub-linear in T T , the number of episodes, assuming access to a confidence bound oracle that achieves an o ( T ) o(T) -regret. Such an oracle is readily available from existing contextual bandit literature. We overcome the technical challenge with arbitrarily many possible contexts, which leads to a reinforcement learning problem with an unbounded state space. Our framework provides improved regret bounds in certain settings when the DM is provided with unlabeled feature data, which is novel to the contextual BwK literature. 1 Introduction Contextual bandits with knapsacks (Contextual BwKs) is a fundamental model for contextual online resource allocation under model uncertainty. Its applications include personalized dynamic pricing [ 9 , 39 , 47 ] , personalized loan discounts [ 40 ] , dynamic procurement [ 5 , 6 ] , and first price auctions [ 48 , 11 ] (see Appendix A.1 for details). In existing research, contextual BwKs are only studied in the single episode setting. In an episode, the decision maker (DM) begins with certain amounts of resources, and then makes allocation decisions contingent upon each arriving request’s context. While the single episode setting is of great importance, in practice, contextual online resource allocation is performed over multiple episodes, where the resources are restocked after an episode ends. For example, in personalized dynamic pricing of a product, the product units are restocked after an episode of the current selling process ends, in anticipation of the next episode. In first price auctions for online ad allocations, an advertiser restores his/her advertising budget after exhausting the current budget. When the DM makes allocation decisions and observes their outcomes in multiple episodes, the DM is accumulating data on the underlying conversion model, which maps a request’s context and an allocation decision to the corresponding expected outcome. Can the DM converge to optimality, as the number of episodes increases? We shed a positive light on this question. We first observe that existing works on the single episode case cannot achieve the desired convergence, see forthcoming Section 3.2 . Different from existing works on contextual BwKs, we directly analyze the Bellman equation associated with the contextual BwK problem in an episode, which is a reinforcement learning (RL) problem with an intractable state space. Specifying the transition probability requires knowing the probability distributions of the contexts, which requires a sample size linear in the number of contexts. Despite the difficulty, we achieve a regret bound independent of the number of contexts, by a careful consideration on how estimation errors propagate as we backtrack the value-to-go functions. Instead of assuming a specific contextual reward and resource consumption model, our algorithm framework accommodates a variety of contextual multi-armed bandit models, such as contextual linear bandits [ 1 ] , contextual generalized linear bandits [ 20 ] , contextual Gaussian process bandits [ 34 ] , kernelized bandits [ 15 ] , neural bandits [ 51 ] , via the notion of confidence bound oracles , see Section 3.2 . Our analytical framework demonstrates the benefits of having sufficiently many unlabeled feature data, which is novel in contextual BwK settings. Related Works. Our contributions are related to the research works on contextual BwKs, online reinforcement learning (RL) on large state spaces, and contextual online RL. The BwK problem is first introduced by [ 6 ] . Its generalization to concave rewards and convex constraints is studied in [ 2 ] , and its adversarial variant is studied in [ 29 ] . The contextual multi-armed bandit generalization of BwKs, dubbed contextual BwKs, is first studied in [ 7 ] . Its generalization to concave rewards and convex constraints is studied by [ 4 ] . [ 3 ] provides an efficient algorithm for linear contextual BwKs. [ 40 ] proposes the contextual BwK model for a conversion model, which is incorporated in our model formulation. [ 40 ] models the conversion model by the contextual logistic bandit model. In our setting, we show that a variety of confidence-bound based research works on contextual multi-armed bandit models, such as the contextual linear bandit models [ 1 ] , the contextual generalized linear bandit models [ 19 ] , its specialization the contextual logistic bandit models [ 19 ] , the contextual Gaussian process bandit models [ 34 ] , kernelized bandit model [ 15 ] , neural bandit model [ 51 ] , can be used to model the conversion model and achieve non-trivial regret bounds, by constructing the corresponding confidence bound oracles based on those works. A recent stream of research works [ 27 , 45 , 25 , 24 ] studies the contextual BwKs assuming access to the online regression oracle [ 22 ] , which is different and in general incomparable to our oracle assumption. Contextual BwKs have also been studied in dynamic pricing settings with inventory constraint settings [ 39 , 47 ] . We provide a detailed comparison with these works on contextual BwKs in Section 3.2 . Lastly, [ 12 ] considers the application of resolving heuristics on an online contextual decision making model with knapsack constraints. While they achieve a logarithmic regret compared with the optimum under mild assumptions on the corresponding fluid relaxation (see Appendix A.3 ), they require either the full feedback setting, or a partial feedback setting that is strictly more informative than the bandit feedback setting. Our online contextual resource allocation problem can be formulated as an online RL problem with large state spaces. A cornucopia of research works have been done on function approximation on the value-to-go functions by (generalized) linear functions [ 50 , 49 , 16 , 36 ] , and general functions via the structural conditions of Eluder Dimensions [ 44 , 41 ] , Bellman Eluder dimension [ 31 ] , Bilinear classes [ 18 ] , Decision-Estimation Coefficient [ 23 ] , and Admissible Bellman Characterization [ 13 ] . There have been substantial works on function approximation on the transition probability kernels instead of the value-to-go functions. [ 32 ] study the case of linear function approximation, while [ 28 , 14 , 38 ] study the case of multinomial logit function approximation. While our online RL problem also suffers from the intractability with large state space, our underlying value-to-go functions and transition probability kernels (see Section 2.2 ) do not match the approximations mentioned above. A crucial challenge lies in the unknown probability distributions in the contexts. These probability distributions do not enjoy the structural conditions in the above works, which motivate us to take a different route for