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

Autor:	Hebbar, Vijeth, Langbort, Cedric
Rok vydání:	2023
Předmět:	Computer Science - Machine Learning Electrical Engineering and Systems Science - Systems and Control
Druh dokumentu:	Working Paper
Popis:	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. Comment: Submitted to L4DC 2024. This is an extended version including proofs and experimental results
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2312.06641 Zobrazit plný text záznamu View this record from Arxiv