# Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach

arXiv: https://arxiv.org/abs/2308.10699 · HTML: https://mlsanity.com/paper/2308.10699/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 21 Aug 2023.

## Builds on (most cited first, 12 of 12)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Exact sampling of determinantal point processes with sublinear time preprocessing](https://mlsanity.com/paper/1905.13476/) (2019)
- [Active Learning and Bayesian Optimization: a Unified Perspective to Learn with a Goal](https://mlsanity.com/paper/2303.01560/) (2023)
- [Context Attentive Bandits: Contextual Bandit with Restricted Context](https://mlsanity.com/paper/1705.03821/) (2017)
- [Online Learning of Network Bottlenecks via Minimax Paths](https://mlsanity.com/paper/2109.08467/) (2021)
- [Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting](https://mlsanity.com/paper/1703.05452/) (2017)
- [Thompson Sampling for Combinatorial Network Optimization in Unknown Environments](https://mlsanity.com/paper/1907.04201/) (2019)
- [ROI Maximization in Stochastic Online Decision-Making](https://mlsanity.com/paper/1905.11797/) (2019)
- [Efficient Online Decision Tree Learning with Active Feature Acquisition](https://mlsanity.com/paper/2305.02093/) (2023)

## Built on by (most cited first, 2 of 2)

- [A Survey on Active Feature Acquisition Strategies](https://mlsanity.com/paper/2502.11067/) (2025)
- [AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints](https://mlsanity.com/paper/2610.07615/) (2026)

## Abstract (arXiv)

Online decision making plays a crucial role in numerous real-world applications. In many scenarios, the decision is made based on performing a sequence of tests on the incoming data points. However, performing all tests can be expensive and is not always possible. In this paper, we provide a novel formulation of the online decision making problem based on combinatorial multi-armed bandits and take the (possibly stochastic) cost of performing tests into account. Based on this formulation, we provide a new framework for cost-efficient online decision making which can utilize posterior sampling or BayesUCB for exploration. We provide a theoretical analysis of Thompson Sampling for cost-efficient online decision making, and present various experimental results that demonstrate the applicability of our framework to real-world problems.