# Semi-Bandit Learning for Monotone Stochastic Optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 76 references that are in the map.
- First posted on arXiv 24 Dec 2023.

## Builds on (most cited first, 30 of 33)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Ironing in the Dark](https://mlsanity.com/paper/1511.06918/) (2015)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [Pandora's Box Problem with Order Constraints](https://mlsanity.com/paper/2002.06968/) (2020)
- [A Stochastic Probing Problem with Applications](https://mlsanity.com/paper/1302.5913/) (2013)
- [Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions](https://mlsanity.com/paper/1608.00673/) (2016)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Pandora's Box with Correlations: Learning and Approximation](https://mlsanity.com/paper/1911.01632/) (2019)
- [Optimal Single-Choice Prophet Inequalities from Samples](https://mlsanity.com/paper/1911.07945/) (2019)
- [Descending Price Optimally Coordinates Search](https://mlsanity.com/paper/1603.07682/) (2016)
- [Single-Sample Prophet Inequalities via Greedy-Ordered Selection](https://mlsanity.com/paper/2111.03174/) (2021)
- [Submodular Stochastic Probing on Matroids](https://mlsanity.com/paper/1310.4415/) (2013)
- [Online Pandora's Boxes and Bandits](https://mlsanity.com/paper/1901.10698/) (2019)
- [Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack](https://mlsanity.com/paper/2107.02058/) (2021)
- [Combinatorial Prophet Inequalities](https://mlsanity.com/paper/1611.00665/) (2016)
- [(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing](https://mlsanity.com/paper/1902.01461/) (2019)

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

- [Reinforcement Learning with Lookahead Information](https://mlsanity.com/paper/2406.02258/) (2024)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [Learning Markov Decision Processes under Fully Bandit Feedback](https://mlsanity.com/paper/2602.02260/) (2026)
- [Contextual Learning for Stochastic Optimization](https://mlsanity.com/paper/2505.16829/) (2025)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

Stochastic optimization is a widely used approach for optimization under uncertainty, where uncertain input parameters are modeled by random variables. Exact or approximation algorithms have been obtained for several fundamental problems in this area. However, a significant limitation of this approach is that it requires full knowledge of the underlying probability distributions. Can we still get good (approximation) algorithms if these distributions are unknown, and the algorithm needs to learn them through repeated interactions? In this paper, we resolve this question for a large class of ''monotone'' stochastic problems, by providing a generic online learning algorithm with √Tlog(T) regret relative to the best approximation algorithm (under known distributions). Importantly, our online algorithm works in a semi-bandit setting, where in each period, the algorithm only observes samples from the random variables that were actually probed. Moreover, our result extends to settings with censored and binary feedback, where the policy only observes truncated or thresholded versions of the probed variables. Our framework applies to several fundamental problems such as prophet inequality, Pandora's box, stochastic knapsack, single-resource revenue management and sequential posted pricing.