Minimizing Regret in Dynamic Decision Problems

Joseph Y. Halpern, Samantha Leung

Abstract

This paper investigates how agents should minimize regret in dynamic, multi-stage decision problems, focusing on the critical role of "forgone opportunities"—past choices that are no longer feasible. The authors demonstrate that accounting for these missed opportunities is essential to prevent irrational behaviors like procrastination. By formalizing the Minimax Weighted Expected Regret (MWER) framework, the paper identifies the exact conditions under which a regret-minimizing agent remains dynamically consistent over time, introducing the concept of χ-rectangularity as a necessary requirement for consistency during learning.

Introduction

In standard decision theory, agents typically maximize expected utility. However, when probabilities are unknown or ambiguous, individuals often turn to alternative rules such as minimax regret. This approach involves choosing the option that minimizes the worst-case difference between the achieved payoff and the payoff that could have been achieved with perfect hindsight.

While minimax regret is well-defined for static decisions, its application to dynamic sequences of choices introduces a dilemma: should an agent's current "menu" of comparison include forgone opportunities? Strict consequentialists argue that only currently available options matter. However, this paper shows that ignoring the past leads to preference reversals (dynamic inconsistency). For instance, an agent might plan to study tomorrow, but when tomorrow arrives, they choose to play instead—a formal manifestation of procrastination. The authors investigate how to structure menus and update beliefs to ensure rational, consistent behavior.

Methods

The authors model dynamic decision problems as single-player extensive-form games represented by decision trees. To evaluate choices, they utilize Minimax Weighted Expected Regret (MWER), where uncertainty is represented by a set of probability measures, each assigned a weight reflecting its reliability.

To address the evolution of decisions over time, the methodology includes:

  1. Menu Selection Formalization: Introducing choice functions that depend on a selected menu, allowing for a comparison between decisions made using only feasible acts versus those using the original, full menu.
  2. Belief Updating: Utilizing "likelihood updating" to adjust the weights of probability measures as new information is acquired.
  3. Axiomatization of Consistency: Proposing axioms, specifically a menu-dependent version of Dynamic Consistency, to mathematically define the avoidance of preference reversals.

Key Insights: The Role of Forgone Opportunities

A central insight of the paper is that procrastination is a menu problem. If an agent ignores forgone opportunities, the regret associated with a sub-optimal current choice may appear deceptively low. However, if the original, superior plan is kept in the comparison menu, the compounding regret of repeated sub-optimal choices can force the agent to adhere to their original plan.

A decision tree illustrating the procrastination example where a student chooses between playing and studying over two days.

As shown in the figure above, a student faces a choice between studying both days or playing. If they choose to play on day one, they reach a second decision node. If they ignore the forgone "study both days" option, the regret of playing again on day two might seem minimal. However, maintaining the full menu ensures the regret of playing twice is compared against the high payoff of the original study plan, thereby incentivizing the student to study on day two.

Furthermore, the authors establish that while keeping forgone opportunities in the menu is sufficient for consistency when no new information is learned, the introduction of learning requires specific belief structures. They prove that an agent's set of weighted probabilities must satisfy a property called χ-rectangularity to guarantee they will not suffer preference reversals under likelihood updating.

Key Results

  • Proposition 3.3: Mathematically proves that if an agent acquires no new information and maintains a constant menu (including forgone opportunities), an MWER decision-maker will never experience preference reversals.
  • Theorems 4.1 & 4.3: Establishes that a set of four rationality axioms is equivalent to a "Separability" condition in regret computation across different events.
  • Theorem 4.5: The paper’s capstone result proves that χ-rectangularity is both necessary and sufficient to guarantee dynamic consistency when an agent learns new information.

Discussion and Future Work

The authors acknowledge that χ-rectangularity is a strict mathematical condition that may not always be satisfied by human beliefs in practice. This opens several avenues for future research:

  • Sophisticated Agents: Exploring agents who are aware of their potential for preference reversals and work backward to find achievable, consistent plans.
  • Weighted Menus: Moving beyond binary menus to assign weights to forgone opportunities. For example, a recently missed opportunity might induce more regret than one abandoned long ago, potentially modeling the psychological decay of regret over time.

Summary updated

BibTeX
@inproceedings{halpern2015minimizing,
  author = {Joseph Y. Halpern and Samantha Leung},
  title = {{Minimizing Regret in Dynamic Decision Problems}},
  booktitle = {ECSQARU},
  year = {2015},
  doi = {10.1007/978-3-319-20807-7\_1},
}
Figure