Constrained Online Decision-Making: A Unified Framework
Not on the map. Why?
Abstract (arXiv)
Contextual online decision-making problems with constraints appear in a wide range of real-world applications, such as adaptive experimental design under safety constraints, personalized recommendation with resource limits, and dynamic pricing under fairness requirements. In this paper, we investigate a general formulation of sequential decision-making with stage-wise feasibility constraints, where at each round, the learner must select an action based on observed context while ensuring that a problem-specific feasibility criterion is satisfied. We propose a unified algorithmic framework that captures many existing constrained learning problems, including constrained bandits, active learning with label budgets, online hypothesis testing with Type I error control, and model calibration. Central to our approach is the concept of upper counterfactual confidence bounds, which enables the design of practically efficient online algorithms with strong theoretical guarantees using any offline conditional density estimation oracle. To handle feasibility constraints in complex environments, we introduce a generalized notion of the eluder dimension, extending it from the classical setting based on square loss to a broader class of metric-like probability divergences. This allows us to capture the complexity of various density function classes and characterize the utility regret incurred due to feasibility constraint uncertainty. Our result offers a principled foundation for constrained sequential decision-making in both theory and practice.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 48 of its 79 references that are in the map. First posted on arXiv 11 May 2025.
Builds on
48 of 79 references.
References · 48
- 2021The Statistical Complexity of Interactive Decision Makingcited by 218
- 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
- 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 181
- 2013Bandits with Knapsackscited by 164
- 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
- 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
- 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 115
- 2017Online Convex Optimization with Stochastic Constraintscited by 95
- 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
- 2020Stochastic Bandits with Linear Constraintscited by 68
- 2019Reinforcement Learning with Convex Constraintscited by 60
- 2019The Nonstochastic Control Problemcited by 52
36 more
- 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 46
- 2024A Survey of Constraint Formulations in Safe Reinforcement Learningcited by 44
- 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
- 2019Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysiscited by 40
- 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 40
- 2019Safe Linear Thompson Sampling with Side Informationcited by 37
- 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
- 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
- 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
- 2024HardNet: Hard-Constrained Neural Networks with Universal Approximation Guaranteescited by 31
- 2015Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Banditscited by 29
- 2014Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Banditscited by 26
- 2021Best Arm Identification with Safety Constraintscited by 25
- 2017Calibration for the (Computationally-Identifiable) Massescited by 23
- 2021Neural Active Learning with Performance Guaranteescited by 22
- 2021Understanding the Eluder Dimensioncited by 19
- 2020Safe Exploration for Optimizing Contextual Banditscited by 14
- 2022Non-monotonic Resource Utilization in the Bandits with Knapsacks Problemcited by 12
- 2020Spoiled for Choice? Personalized Recommendation for Healthcare Decisions: A Multi-Armed Bandit Approachcited by 10
- 2023Neural Contextual Bandits for Personalized Recommendationcited by 10
- 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
- 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
- 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
- 2023Directional Optimism for Safe Linear Banditscited by 8
- 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 8
- 2022Safe Control with Minimal Regretcited by 7
- 2022Safe reinforcement learning for multi-energy management systems with known constraint functionscited by 7
- 2024Falcon: Fair Active Learning using Multi-armed Banditscited by 6
- 2024Safe Multi-Agent Reinforcement Learning with Convergence to Generalized Nash Equilibriumcited by 6
- 2020Regret-optimal measurement-feedback controlcited by 5
- 2025Contextual Online Decision Making with Infinite-Dimensional Functional Regressioncited by 5
- 2024Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copiescited by 4
- 2025Learning to Price with Resource Constraints: From Full Information to Machine-Learned Pricescited by 3
- 2023Regret Optimal Control for Uncertain Stochastic Systemscited by 2
- 2024Online Learning with Unknown Constraintscited by 2
- 2023Online Learning for Equilibrium Pricing in Markets under Incomplete Informationcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.