# Constrained Online Decision-Making: A Unified Framework

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

## Key facts

- Cited by 1 papers 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 (most cited first, 30 of 48)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019)
- [GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond](https://mlsanity.com/paper/2211.01962/) (2022)
- [A Survey of Constraint Formulations in Safe Reinforcement Learning](https://mlsanity.com/paper/2402.02025/) (2024)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension](https://mlsanity.com/paper/2005.10804/) (2020)
- [Safe Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.06239/) (2021)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [HardNet: Hard-Constrained Neural Networks with Universal Approximation Guarantees](https://mlsanity.com/paper/2410.10807/) (2024)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits](https://mlsanity.com/paper/1401.1123/) (2014)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [Calibration for the (Computationally-Identifiable) Masses](https://mlsanity.com/paper/1711.08513/) (2017)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [Understanding the Eluder Dimension](https://mlsanity.com/paper/2104.06970/) (2021)
- [Safe Exploration for Optimizing Contextual Bandits](https://mlsanity.com/paper/2002.00467/) (2020)
- [Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem](https://mlsanity.com/paper/2209.12013/) (2022)

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

- [Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation](https://mlsanity.com/paper/2605.00393/) (2026)

## 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.