# Online Decision Making with History-Average Dependent Costs (Extended)

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 21 references that are in the map.
- First posted on arXiv 11 Dec 2023.

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

- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)

## Abstract (arXiv)

In many online sequential decision-making scenarios, a learner's choices affect not just their current costs but also the future ones. In this work, we look at one particular case of such a situation where the costs depend on the time average of past decisions over a history horizon. We first recast this problem with history dependent costs as a problem of decision making under stage-wise constraints. To tackle this, we then propose the novel Follow-The-Adaptively-Regularized-Leader (FTARL) algorithm. Our innovative algorithm incorporates adaptive regularizers that depend explicitly on past decisions, allowing us to enforce stage-wise constraints while simultaneously enabling us to establish tight regret bounds. We also discuss the implications of the length of history horizon on design of no-regret algorithms for our problem and present impossibility results when it is the full learning horizon.