mlsanityData to 14 Oct 2026

Episodic Contextual Bandits with Knapsacks under Conversion Models

arXiv 2507.06859 ↗First posted 9 Jul 2025cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

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, the number of episodes, assuming access to a confidence bound oracle that achieves an 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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 33 of its 49 references that are in the map. First posted on arXiv 9 Jul 2025.

Builds on

33 of 49 references.

References · 33

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2017On Kernelized Multi-armed Banditscited by 352
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  4. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  5. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  7. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  8. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  9. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  10. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  11. 2014Bandits with concave rewards and convex knapsackscited by 83
  12. 2015Linear Contextual Bandits with Knapsackscited by 82
21 more
  1. 2018Adversarial Bandits with Knapsackscited by 73
  2. 2015An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectivescited by 43
  3. 2020Optimal No-regret Learning in Repeated First-price Auctionscited by 33
  4. 2018Contextual Bandits with Cross-learningcited by 31
  5. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  6. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  7. 2020Online Stochastic Optimization with Wasserstein Based Non-stationaritycited by 25
  8. 2018A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Managementcited by 18
  9. 2023Learning to Bid in Repeated First-Price Auctions with Budgetscited by 14
  10. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  11. 2024Online Estimation via Offline Estimation: An Information-Theoretic Frameworkcited by 13
  12. 2022Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oraclescited by 12
  13. 2022Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDPcited by 11
  14. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  15. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 8
  16. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  17. 2021Exponential Family Model-Based Reinforcement Learning via Score Matchingcited by 5
  18. 2023Online Learning under Budget and ROI Constraints via Weak Adaptivitycited by 5
  19. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
  20. 2022Contextual Bandits with Knapsacks for a Conversion Modelcited by 3
  21. 2022Contextual Decision-Making with Knapsacks Beyond the Worst Casecited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Non-Stationary Online Resource Allocation: Learning from a Single Samplecited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
  2. 2026Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
  3. 2026Gated Decoupled Compositional Bandits: A Unified Theory of Contextual Bandits with Supervised-Calibrated Action Scaling and Pre-Execution Gating
  4. 2023Contextual Bandits and Imitation Learning via Preference-Based Active Queries
  5. 2024Diffusion Models Meet Contextual Bandits
  6. 2022Flexible and Efficient Contextual Bandits with Heterogeneous Treatment Effect Oracles
  7. 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits
  8. 2020Statistical Inference for Online Decision-Making: In a Contextual Bandit Setting