Abstract
In classical decision theory, agents are typically modeled as either greedy cost-minimizers or as "Maximum Entropy" explorers. This paper challenges the standard convention by proposing that entropy minimization, rather than maximization, provides a more principled framework for modeling risk-averse, adaptive agents. By optimizing entropy under a fixed exploration budget, the authors provide a formal mathematical derivation for the ubiquitous $\epsilon$-greedy strategy in reinforcement learning and offer insights into human-like behaviors such as cognitive dissonance and the "lesser of two evils" heuristic.
Introduction
Standard decision theory dictates that an agent should always select the action with the lowest expected cost. While mathematically straightforward, this "greedy" approach is notoriously fragile in dynamic environments. If initial cost estimates are inaccurate or the environment shifts, a purely exploitative agent fails to discover superior alternatives.
To address this, fields like Reinforcement Learning (RL) employ heuristics such as the $\epsilon$-greedy strategy, where an agent chooses the optimal action most of the time but explores a random action with probability $\epsilon$. Despite its success, $\epsilon$-greedy has largely remained an ad-hoc fix. This paper seeks to provide a rigorous theoretical foundation for such strategies by linking exploration to formal measures of risk and information theory, specifically through the lens of entropy minimization.
The Framework: Entropy as a Measure of Risk
The authors frame the decision-making process as an optimization problem for an agent willing to sacrifice a specific amount of expected utility—termed the "exploration budget" ($E$)—to remain adaptive. The central question is how the agent should distribute its probability across possible actions given this budget.
Traditionally, the principle of Maximum Entropy is used to represent a state of least knowledge or risk-neutrality, leading to the smooth "Gibbs" or "logit" distributions common in economics. However, this paper argues that Entropy Minimization is the hallmark of risk-aversion. While a maximizer spreads probability as thinly as possible, a minimizer seeks to concentrate probability on the safest or most certain outcomes allowed by the constraints.
Constraints and Optimization
The model operates under two primary constraints:
- Fixed Average Cost: The average cost of chosen actions must equal the exploration budget $E$.
- Monotonicity: Actions with lower costs must always have a higher or equal probability than actions with higher costs ($p_i \geq p_j$ if $c_i \leq c_j$).
Unlike entropy maximization, which yields a single global optimum, entropy minimization results in multiple local minima. This leads to "sparse" probability distributions where certain high-cost actions are ignored entirely, reflecting a more selective and "intelligent" exploration strategy.
Key Insights: The Origin of $\epsilon$-greedy
One of the paper's most significant contributions is the formal proof that the $\epsilon$-greedy strategy is a local minimum of the entropy function. This suggests that the heuristic used by AI researchers for decades is not just a lucky guess, but a mathematically optimal response for a risk-averse agent operating under a constrained exploration budget.
Furthermore, the model explains the "Lesser of Two Evils" phenomenon. When faced with two high-cost options, a risk-seeking (entropy maximizing) agent treats them as nearly identical. In contrast, a risk-averse (entropy minimizing) agent will decisively favor the slightly better option. This sensitivity to small differences in high-risk scenarios is a fundamental component of adaptive behavior.
Behavioral Analogies: Dissonance and Frustration
The existence of multiple local minima in the entropy function allows the authors to draw parallels to psychological states:
- Cognitive Dissonance: As the environment or the budget $E$ changes, the agent's optimal strategy may "jump" discontinuously from one local minimum to another. This sudden narrowing of focus to minimize uncertainty mirrors the human experience of resolving cognitive dissonance.
- Frustration: In scenarios with competing goals or nearly identical costs, the agent may experience "frustration," where no single clear optimal choice emerges, leading to instability in the decision-making process.
Results and Phase Transitions
The paper demonstrates that as the exploration budget $E$ increases, the agent undergoes "first-order phase transitions." These are sudden, non-linear shifts in strategy rather than gradual adjustments. The authors also identify "re-entrance" effects, where a strategy that was previously discarded becomes optimal again as the parameters shift. These dynamics suggest that adaptive behavior is naturally characterized by punctuated equilibrium rather than smooth transitions.
Limitations and Future Work
While the framework provides a robust justification for existing heuristics, it currently assumes a fixed action space. In real-world creative problem solving, the set of possible actions is often unknown and must be discovered. Additionally, the authors note that entropy minimization may contribute to the Einstellung effect—the tendency to stick to a known solution even when a better one becomes available. Future research could investigate how these entropy-based dynamics might be used to identify and break out of such mental dead-ends.
Conclusion
By shifting the focus from entropy maximization to minimization, this research provides a new theoretical bridge between information theory, reinforcement learning, and cognitive psychology. It suggests that "intelligent" exploration is not about randomizing choices, but about strategically minimizing risk while maintaining the flexibility to adapt to new information.
Summary updated