Online Decision Making with History-Average Dependent Costs (Extended)
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.
Code (1)
Tasks
Decision MakingSequential Decision MakingSimilar Papers 제목 키워드 기반
Online Prediction With History-Dependent Experts: The General Case
We study the problem of prediction of binary sequences with expert advice in the online setting, which is a classic example of online machine learning. We interpret the binary sequence as the price history of a stock, an…
PredictionStock PredictionInverse Reinforcement Learning with Switching Rewards and History Dependency for Characterizing Animal Behaviors
Traditional approaches to studying decision-making in neuroscience focus on simplified behavioral tasks where animals perform repetitive, stereotyped actions to receive explicit rewards. While informative, these methods …
Decision MakingAddressing Myopic Constrained POMDP Planning with Recursive Dual Ascent
Lagrangian-guided Monte Carlo tree search with global dual ascent has been applied to solve large constrained partially observable Markov decision processes (CPOMDPs) online. In this work, we demonstrate that these globa…
Decision MakingBandit Linear Optimization for Sequential Decision Making and Extensive-Form Games
Tree-form sequential decision making (TFSDM) extends classical one-shot decision making by modeling tree-form interactions between an agent and a potentially adversarial environment. It captures the online decision-makin…
counterfactualDecision MakingFormSequential Decision MakingIBCB: Efficient Inverse Batched Contextual Bandit for Behavioral Evolution History
Traditional imitation learning focuses on modeling the behavioral mechanisms of experts, which requires a large amount of interaction history generated by some fixed expert. However, in many streaming applications, such …
Decision MakingImitation LearningOut-of-Distribution GeneralizationRecommendation Systems