# Adaptive Decision-Making with Constraints and Dependent Losses: Performance Guarantees and Applications to Online and Nonlinear Identification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 14 references that are in the map.
- First posted on arXiv 6 Apr 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)

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

- [Stochastic Online Optimization for Cyber-Physical and Robotic Systems](https://mlsanity.com/paper/2404.05318/) (2024)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)

## Abstract (arXiv)

We consider adaptive decision-making problems where an agent optimizes a cumulative performance objective by repeatedly choosing among a finite set of options. Compared to the classical prediction-with-expert-advice set-up, we consider situations where losses are constrained and derive algorithms that exploit the additional structure in optimal and computationally efficient ways. Our algorithm and our analysis is instance dependent, that is, suboptimal choices of the environment are exploited and reflected in our regret bounds. The constraints handle general dependencies between losses (even across time), and are flexible enough to also account for a loss budget, which the environment is not allowed to exceed. The performance of the resulting algorithms is highlighted in two numerical examples, which include a nonlinear and online system identification task.