Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners

1. Problem Statement

The paper investigates the long-term survival and market dominance of heterogeneous learning agents competing in asset markets with stochastic payoffs. It addresses a fundamental gap between two major theoretical frameworks:

• Economics (Bayesian Learning): Assumes agents have a prior over the underlying stochastic process and update beliefs via Bayes' rule. Success is measured by maximizing expected utility (wealth growth).
• Computer Science (No-Regret Learning): Makes no assumptions about the underlying process (allowing for adversarial environments) and minimizes "regret" relative to the best fixed strategy in hindsight.

Core Question: In a competitive market where both types of agents coexist, which learning paradigm ensures survival (i.e., maintaining a non-zero wealth share), and how do their performance metrics (regret vs. belief accuracy) relate to market selection?

2. Methodology and Model

The authors utilize a complete asset market model (specifically using Arrow securities) with the following characteristics:

• Environment: Discrete time steps $t=1, 2, \dots$. A state $s_t$ is realized from a finite set of states $S$ according to an i.i.d. distribution $q$.
• Agents: $N$ agents with initial wealth $w_0^n$. Agents choose investment portfolios $\alpha_t^n$ to maximize the growth rate of their wealth.
• Dynamics: Wealth evolves multiplicatively. The ratio of wealth between two agents $n$ and $m$ depends on the cumulative difference in their log-wealth growth rates.
• Key Metric: The paper establishes a direct link between Regret and Wealth Share.
  • Let $R_T(\alpha)$ be the regret of an investment sequence $\alpha$ relative to the best fixed strategy in hindsight.
  • The log-wealth ratio is expressed as: $\log(r_{nm}^T) = R_T(\alpha^m) - R_T(\alpha^n) + \text{const}$.
  • Survival Condition: An agent survives if and only if their regret remains bounded relative to every competitor. If the regret difference diverges to infinity, the agent's wealth share converges to zero (vanishes).

3. Key Contributions and Theoretical Results

A. The Relationship Between Regret and Survival

The paper formalizes that low regret alone does not guarantee survival.

• Theorem 3.1: An agent survives if and only if $\limsup_{T \to \infty} (R_T^n - R_T^m) < \infty$ for all competitors $m$.
• Implication: Even if two agents both achieve $O(\log T)$ regret, the agent with the larger constant factor in the regret bound will almost surely vanish. The absolute level of regret matters, not just the asymptotic rate.

B. Performance of Perfect Bayesian Learners

• Theorem 5.3: A Bayesian learner with a finite support prior that includes the true distribution $q$ achieves constant expected regret.
• Result: Such a "perfect" Bayesian dominates the market. They drive out any competitor whose regret grows over time (even if that growth is sublinear, like $O(\log T)$ or $O(\sqrt{T})$). This validates the "Market Selection Hypothesis" in economics: rational Bayesians with correct models survive.

C. Fragility of Bayesian Learning

The paper demonstrates that Bayesian learning is highly fragile to misspecification:

1. Inaccurate Priors (Theorem 6.1): If the true distribution $q$ is not in the support of the prior, the Bayesian converges to the "closest" model in relative entropy. This results in linear regret ($\Theta(T)$), causing the agent to vanish against any no-regret learner.
2. Noisy Updates (Theorem 6.5): Even if the correct model is in the prior, if the update rule contains small "trembling hand" errors (zero-mean noise in weighting data vs. prior), the Bayesian fails to converge. The beliefs oscillate, leading to linear regret and eventual extinction.
3. Distribution Shifts (Proposition 7.1): Standard Bayesian learning adapts slowly to shifts in the data-generating process. If the distribution shifts, the posterior (which was concentrated on the old model) becomes the new prior, causing the agent to spend significant time on incorrect models, accumulating linear regret.

D. Robustness of No-Regret Learning

• No-regret learners (e.g., using Online Convex Optimization or UCB) do not require a model of the environment.
• They guarantee sublinear regret (e.g., $O(\log T)$ or $O(\sqrt{T})$) regardless of the process.
• While they lose to a "perfect" Bayesian, they survive against "imperfect" Bayesians (those with wrong priors or noisy updates) because the imperfect Bayesians incur linear regret.

4. Proposed Hybrid Strategies

Motivated by the trade-off between the speed of Bayesian learning and the robustness of no-regret learning, the authors propose two hybrid methods:

1. Regularized Bayesian Update (for Distribution Shifts):

   • Mechanism: Adds a small regularization term $\epsilon_t$ to the Bayesian update weights, preventing any hypothesis weight from decaying to exactly zero.
   • Result: Maintains constant regret in stationary settings (like standard Bayes) but achieves logarithmic regret ($O(\log T)$) when distribution shifts occur. This allows the agent to recover quickly from shifts without being driven out.

2. Bayes-to-No-Regret Switching (for Prior Misspecification):

   • Mechanism: Runs a Bayesian strategy and a no-regret strategy in parallel. It tracks the cumulative utility gap ($D_t$). If the Bayesian strategy falls sufficiently behind the no-regret benchmark (exceeding a dynamic threshold), the agent switches permanently to the no-regret strategy.
   • Result:
     • If the prior is correct: The agent stays Bayesian with high probability, achieving constant regret.
     • If the prior is misspecified: The agent switches to the no-regret strategy, inheriting its sublinear regret guarantee.

5. Significance and Implications

• Bridging Disciplines: The paper provides the first formal connection between the economic concept of "survival" and the computer science concept of "regret minimization" in asset markets.
• Refining Market Selection: It challenges the simplistic view that "rational" (Bayesian) agents always win. It shows that robustness is as critical as accuracy. A slightly misspecified Bayesian is worse off than a robust no-regret learner.
• Practical Application: The findings suggest that in real-world markets (where models are rarely perfect and environments shift), pure Bayesian approaches are risky. The proposed hybrid strategies offer a "best-of-both-worlds" approach, combining the fast convergence of Bayes with the safety net of regret minimization.
• Policy and Design: For algorithmic trading and market design, the results imply that the choice of learning algorithm has profound long-term consequences for market composition and price stability.

6. Conclusion

The paper concludes that while Bayesian learning is optimal under perfect specification, it is brittle in realistic environments. No-regret learning provides a robust fallback but may be outperformed by accurate Bayesians. The optimal strategy for heterogeneous agents is a hybrid approach that leverages Bayesian updates for speed while incorporating mechanisms (regularization or switching) to detect and recover from model failure or environmental shifts.