Adaptive decision making via entropy minimization.

Armen E. Allahverdyan, Aram Galstyan, Ali E. Abbas, Zbigniew R. Struzik

TL;DR

This paper proposes a novel approach to adaptive decision-making by framing it as an entropy minimization problem. This method, unlike standard entropy maximization, leads to agents exhibiting "intelligent" behaviors like exploring costly options and showing cognitive dissonance, offering a more nuanced model of decision-making under uncertainty.

What Problem Does This Paper Address?

Traditional decision theory suggests agents should always pick the action with the lowest estimated cost (or highest utility). However, this rigid approach fails in complex, uncertain environments where adapting to new information or exploring less obvious options is crucial. Think of situations like creative problem-solving, where sticking to the "obvious" solution can lead to a dead end, or the classic exploration-exploitation dilemma in reinforcement learning. The authors aim to model an agent that can make more adaptive decisions by sacrificing a small amount of immediate utility for the sake of learning and better future outcomes. They specifically investigate how an agent should choose a mixed action strategy (i.e., assigning probabilities to different actions) in such scenarios.

Methods

The core of the paper is the proposal of entropy minimization as a principle for adaptive decision-making. While entropy maximization is a well-established technique for inferring probabilities under uncertainty (often seen in statistical physics and machine learning), the authors argue that entropy minimization better captures risk-averse behavior. They formulate the problem as an agent choosing probabilities for actions, subject to two main constraints:

  1. Fixed expected utility for exploration: The agent commits to investing a certain amount of expected utility (beyond the minimum cost) into exploring less optimal actions.
  2. Cost-probability correlation: Actions with lower costs should generally have higher probabilities.

They then show that entropy minimization, under these constraints, leads to specific probability distributions that exhibit behaviors not seen with entropy maximization. They also explore the mathematical properties of these solutions, including their relationship to stochastic dominance and majorization, and use Lagrange multipliers to derive the optimal probabilities.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Entropy Minimization as Risk Aversion: The paper posits that minimizing entropy, rather than maximizing it, is a more appropriate model for risk-averse agents who are willing to explore uncertain options.
  • "Intelligent" Behaviors Emerge: Entropy minimization naturally leads to behaviors that resemble rudimentary intelligence:
  • Accepting Costly Options: Agents assign non-negligible probabilities to actions with higher costs, reflecting a willingness to explore.
  • "Lesser of Two Evils" Choice: When faced with two actions of comparable cost, the agent tends to pick the one with the slightly lower cost.
  • Cognitive Dissonance and Frustration: The agent's probability distributions can change abruptly with small shifts in expected utility, and they can exhibit behaviors akin to cognitive dissonance (e.g., nullifying probabilities of high-cost actions as more utility is invested in adaptation).
  • Contrast with Entropy Maximization: Entropy maximization, while useful for inferring probabilities based on known constraints, doesn't produce these "intelligent" adaptive behaviors. It tends to favor the most probable outcomes and doesn't exhibit the same nuanced responses to comparable costs or the dynamic shifts seen in minimization.
  • e-Greedy Connection: The entropy minimization approach recovers the well-known ε-greedy strategy from reinforcement learning under specific conditions, providing a theoretical grounding for this heuristic.

Key Results

The paper demonstrates that by minimizing entropy under specific constraints, an agent can achieve adaptive decision-making. For instance, in a three-action scenario, they show how different cost structures lead to distinct probability distributions for the agent. They illustrate that the entropy-minimizing agent can:

  • Assign a higher probability to the lowest-cost action than an entropy-maximizing agent.
  • Account for higher-cost actions in a way that reflects risk aversion.
  • Exhibit distinct behaviors when comparing actions with similar costs, favoring the slightly cheaper one.
  • Undergo "re-entrance" phenomena where the optimal strategy shifts back and forth as the exploration utility increases, suggesting a form of frustration or competing goals.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on deriving the mathematical framework and demonstrating emergent behaviors. Empirical validation on real-world decision-making tasks is a natural next step.
  • Rudimentary Intelligence: The "intelligent behaviors" observed are described as rudimentary. Further work could explore how these principles scale and apply to more complex cognitive tasks.
  • Creativity Modeling: The authors suggest that this framework could be extended to model creativity, which involves not just choosing from a fixed action space but also conceiving and understanding the action space itself. This remains an open area.
  • Generalization: While the paper explores n=3 and n=4 actions, further investigation into the behavior for larger numbers of actions and different cost distributions could be valuable.
  • Comparison to Other Models: While contrasted with entropy maximization, a deeper comparison with other adaptive decision-making models in psychology, economics, and AI could further situate their contribution.

Summary updated

Abstract

An agent choosing between various actions tends to take the one with the lowest cost. But this choice is arguably too rigid (not adaptive) to be useful in complex situations, e.g., where exploration–exploitation trade-off is relevant in creative task solving or when stated preferences differ from revealed ones. Here we study an agent who is willing to sacrifice a fixed amount of expected utility for adaptation. How can/ought our agent choose an optimal (in a technical sense) mixed action? We explore consequences of making this choice via entropy minimization, which is argued to be a specific example of risk-aversion. This recovers the ϵ -greedy probabilities known in reinforcement learning. We show that the entropy minimization leads to rudimentary forms of intelligent behavior: (i) the agent assigns a non-negligible probability to costly events; but (ii) chooses with a sizable probability the action related to less cost (lesser of two evils) when confronted with two actions with comparable costs; (iii) the agent is subject to effects similar to cognitive dissonance and frustration. Neither of these features are shown by entropy maximization. Previous article in issue Next article in issue
BibTeX
@article{allahverdyan2018adaptive,
  author = {Armen E. Allahverdyan and Aram Galstyan and Ali E. Abbas and Zbigniew R. Struzik},
  title = {{Adaptive decision making via entropy minimization.}},
  journal = {Int. J. Approx. Reason.},
  year = {2018},
  url = {https://openreview.net/forum?id=c1STU6WBDe8Z},
}
Figure