Performance Analysis of Trial and Error Algorithms

Jérôme Gaveau, Christophe J. Le Martret, Mohamad Assaad

Introduction

In modern decentralized systems—ranging from autonomous traffic management to wireless communication networks—individual agents must often optimize their behavior without a central controller or a complete model of their environment. In these "model-free" settings, agents learn through interaction, adjusting their actions based on local feedback. Two prominent algorithms for this task are Trial and Error Learning (TEL) and Optimal Dynamical Learning (ODL). While both are designed to drive a system toward an optimal state, evaluating their performance analytically has historically been a significant challenge due to the "curse of dimensionality."

This paper introduces a novel framework for approximating the massive, high-dimensional Markov Chains (MCs) that govern these algorithms. By reducing the state space to a tractable size, the authors provide the first clear comparison of how these algorithms scale as the number of players increases, revealing that TEL offers superior stability and efficiency in large-scale networks.

The Challenge: State Space Explosion

The behavior of decentralized learning algorithms is typically modeled using Markov Chains. However, the number of possible states in these systems grows exponentially with the number of players ($K$) and resources ($N$). For instance, even a modest system with 3 players and 3 resources can result in a state space exceeding 370,000 states.

This complexity makes it nearly impossible to calculate two critical performance metrics:

  1. Expected First Hitting Time (EFHT): The average time required for the system to reach the optimal configuration.
  2. Stability ($\alpha$): The proportion of time the system remains in the optimal state once it has been reached.

Previously, researchers had to rely on computationally expensive Monte Carlo simulations to estimate these values. The lack of an analytical framework prevented a deep understanding of how these algorithms would behave in real-world, large-scale deployments.

Methodology: Dimensionality Reduction

To overcome this hurdle, the authors propose a two-step dimensionality reduction technique to create an Approximated Markov Chain ($\tilde{\Xi}$). This method focuses on the essential dynamics of the system while discarding redundant information.

1. Reduced Recurrent Classes (RRC)

The authors observe that many states are functionally identical due to the interchangeability of players and resources. By grouping states based on the repartition of players over resources (e.g., treating "two players on resource A" the same as "two players on resource B"), the state space is significantly compressed.

2. Intermediary State Modeling

To ensure the model remains "ergodic" (meaning every state is reachable), the authors carefully incorporate a subset of "intermediary" states. These represent the internal "moods" of the agents—such as "Watchful" or "Discontent"—which facilitate the transitions between stable configurations.

By applying Assumption 1—which posits that at most one player experiments with a new action at any given time—the authors reduce the intractable global MC into a simplified matrix calculation that can be solved numerically with high precision.

Key Insights: TEL vs. ODL

The analytical framework reveals a striking "Complexity Paradox." While ODL is mathematically "optimal" in its design and utilizes fewer internal moods (Content and Discontent) than TEL (Content, Watchful, Hopeful, and Discontent), it performs significantly worse in large systems.

  • Scaling Behavior: The most critical finding is that TEL’s convergence time (EFHT) grows polynomially with the number of players. In contrast, ODL’s convergence time grows exponentially. This makes ODL effectively unusable for large-scale decentralized systems where the number of agents is high.
  • The Buffer Effect: TEL’s additional moods act as a behavioral buffer. While ODL is prone to immediate instability when a single agent becomes discontent, TEL’s "Watchful" and "Hopeful" states allow the system to absorb minor fluctuations, leading to much higher stability ($\alpha$).
  • Resource Impact: The study also finds that increasing the number of available resources ($N > K$) reduces collisions among agents, which improves both the speed of convergence and the overall stability for both algorithms.

Results and Validation

The proposed approximation ($\tilde{\Xi}$) was validated against extensive Monte Carlo simulations (ranging from 5,000 to $10^6$ trials). The results show that the approximation is highly accurate, particularly as the experimentation probability ($\epsilon$) approaches zero. The findings confirm that while ODL and TEL may perform similarly in very small systems, TEL is the clear winner as the network scales, reaching the optimum faster and maintaining it more consistently.

Limitations and Future Work

The primary limitation of this framework is its reliance on the assumption that simultaneous experiments by multiple agents are rare. As the experimentation rate ($\epsilon$) increases, the likelihood of concurrent changes rises, and the approximation begins to lose accuracy.

Future research could extend this framework to more complex utility models and geographical interference patterns, where the impact of an agent's action depends on their physical distance from others. This would further bridge the gap between theoretical decentralized learning and practical applications in fields like wireless communications and the Internet of Things (IoT).

Summary updated

BibTeX
@article{gaveau2020performance,
  author = {Jérôme Gaveau and Christophe J. Le Martret and Mohamad Assaad},
  title = {{Performance Analysis of Trial and Error Algorithms}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2020},
  doi = {10.1109/tpds.2020.2964256},
}
Figure