Minimizing Regret in Dynamic Decision Problems

2015/01/31 by Halpern, Joseph Y., Leung, Samantha · 1 citation
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1502.00152

Abstract

The menu-dependent nature of regret-minimization creates subtleties when it is applied to dynamic decision problems. Firstly, it is not clear whether forgone opportunities should be included in the menu, with respect to which regrets are computed, at different points of the decision problem. If forgone opportunities are included, however, we can characterize when a form of dynamic consistency is guaranteed. Secondly, more subtleties arise when sophistication is used to deal with dynamic inconsistency. In the full version of this paper, we examine, axiomatically and by common examples, the implications of different menu definitions for sophisticated, regret-minimizing agents.

Cited by

• Correlated equilibrium implementation: Navigating toward social optima with learning dynamics

Related

• On the Computational Efficiency of Adaptive and Dynamic Regret Minimization
• Bridging Utility Maximization and Regret Minimization
• Iterated Regret Minimization: A More Realistic Solution Concept
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously