mlsanityData to 14 Oct 2026

Clustered Linear Contextual Bandits with Knapsacks

arXiv 2308.10722 ↗First posted 21 Aug 2023cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

In this work, we study clustered contextual bandits where rewards and resource consumption are the outcomes of cluster-specific linear models. The arms are divided in clusters, with the cluster memberships being unknown to an algorithm. Pulling an arm in a time period results in a reward and in consumption for each one of multiple resources, and with the total consumption of any resource exceeding a constraint implying the termination of the algorithm. Thus, maximizing the total reward requires learning not only models about the reward and the resource consumption, but also cluster memberships. We provide an algorithm that achieves regret sublinear in the number of time periods, without requiring access to all of the arms. In particular, we show that it suffices to perform clustering only once to a randomly selected subset of the arms. To achieve this result, we provide a sophisticated combination of techniques from the literature of econometrics and of bandits with constraints.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 25 of its 51 references that are in the map. First posted on arXiv 21 Aug 2023.

Builds on

25 of 51 references.

References · 25

  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  2. 2013Bandits with Knapsackscited by 164
  3. 2014Online Clustering of Banditscited by 102
  4. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  5. 2014Bandits with concave rewards and convex knapsackscited by 83
  6. 2015Linear Contextual Bandits with Knapsackscited by 82
  7. 2018Adversarial Bandits with Knapsackscited by 73
  8. 2014Resourceful Contextual Banditscited by 45
  9. 2016On Context-Dependent Clustering of Banditscited by 44
  10. 2020Meta-learning for mixed linear regressioncited by 44
  11. 2015An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectivescited by 43
  12. 2018Learning Mixtures of Linear Regressions with Nearly Optimal Complexitycited by 37
13 more
  1. 2015Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Banditscited by 29
  2. 2021Local Clustering in Contextual Multi-Armed Banditscited by 29
  3. 2019Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Momentscited by 26
  4. 2017Online Clustering of Contextual Cascading Banditscited by 24
  5. 2020Online Learning with Vector Costs and Bandits with Knapsackscited by 20
  6. 2020Budget-Constrained Bandits over General Cost and Reward Distributionscited by 14
  7. 2018Unifying the stochastic and the adversarial Bandits with Knapsackcited by 12
  8. 2020Unifying Clustered and Non-stationary Banditscited by 11
  9. 2020Learning Mixtures of Low-Rank Modelscited by 11
  10. 2021Thompson Sampling for Bandits with Clustered Armscited by 6
  11. 2013Adaptive Crowdsourcing Algorithms for the Bandit Survey Problemcited by 5
  12. 2020Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendationcited by 5
  13. 2018Panel Data Quantile Regression with Grouped Fixed Effectscited by 1

Built on by

Not cited yet.