# Online Decision Making with Generative Action Sets

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 30 Sep 2025.

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

- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Wide & Deep Learning for Recommender Systems](https://mlsanity.com/paper/1606.07792/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [MeLU: Meta-Learned User Preference Estimator for Cold-Start Recommendation](https://mlsanity.com/paper/1908.00413/) (2019)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Growing Action Spaces](https://mlsanity.com/paper/1906.12266/) (2019)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Deep Reinforcement Learning for Dynamic Treatment Regimes on Medical Registry Data](https://mlsanity.com/paper/1801.09271/) (2018)
- [Exploratory Machine Learning with Unknown Unknowns](https://mlsanity.com/paper/2002.01605/) (2020)
- [Active Data Discovery: Mining Unknown Data using Submodular Information Measures](https://mlsanity.com/paper/2206.08566/) (2022)
- [Online Pricing and Allocation with Demand Learning and Fulfillment Cost](https://mlsanity.com/paper/2501.18049/) (2025)
- [Dynamic Pricing with Adversarially-Censored Demands](https://mlsanity.com/paper/2502.06168/) (2025)
- [Almost Tight Bounds for Online Facility Location in the Random-Order Model](https://mlsanity.com/paper/2207.08783/) (2022)

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

- [Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand](https://mlsanity.com/paper/2605.05609/) (2026)
- [When Is Coarse Supervision Worth It? Cost-Aware Learning under Unknown Aggregation](https://mlsanity.com/paper/2609.36704/) (2026)
- [Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees](https://mlsanity.com/paper/2610.14790/) (2026)

## Abstract (arXiv)

With advances in generative AI, decision-making agents can now dynamically create new actions during online learning, but action generation typically incurs costs that must be balanced against potential benefits. We study an online learning problem where an agent can generate new actions at any time step by paying a one-time cost, with these actions becoming permanently available for future use. The challenge lies in learning the optimal sequence of two-fold decisions: which action to take and when to generate new ones, further complicated by the triangular tradeoffs among exploitation, exploration and textitcreation. To solve this problem, we propose a doubly-optimistic algorithm that employs Lower Confidence Bounds (LCB) for action selection and Upper Confidence Bounds (UCB) for action generation. Empirical evaluation on healthcare question-answering datasets demonstrates that our approach achieves favorable generation-quality tradeoffs compared to baseline strategies. From theoretical perspectives, we prove that our algorithm achieves the optimal regret of O(T^fracdd+2d^fracdd+2 + d√Tlog T), providing the first sublinear regret bound for online learning with expanding action spaces.