Improving the Speed of Response of Learning Algorithms Using Multiple Models

Kumpati S. Narendra, Yu WangarXiv 2015 · OpenReview

TL;DR

This paper introduces the concept of using multiple "models" to accelerate the learning process in simple reinforcement learning agents, specifically "learning automata." By employing multiple models, the authors demonstrate a significant speedup in convergence compared to traditional single-model approaches, paving the way for more efficient learning systems.

What Problem Does This Paper Address?

Machine learning, particularly in the realm of reinforcement learning, is often criticized for being slow to converge. This means that agents take a long time to learn optimal behaviors, even in relatively simple environments. The authors highlight that while numerous attempts have been made to speed up learning, the success of "multiple model-based methods" in adaptive systems suggests a promising avenue for reinforcement learning. They aim to investigate how this multi-model approach can be applied to improve the speed of response for basic learning schemes, starting with the fundamental "learning automaton."

Methods

The paper focuses on "learning automata," which are agents that learn to choose the best action from a finite set in a random environment based on reward or penalty feedback. The authors explore various reinforcement schemes for updating the automaton's action probabilities, including:

  • Linear Reward-Inaction (LR-I): A simple scheme where probabilities are only updated upon receiving a reward. This scheme is e-optimal but can have absorbing states.
  • Linear Reward-Penalty (LR-P): An ergodic scheme that updates probabilities for both rewards and penalties, leading to more general convergence properties.
  • Linear Reward-Penalty-Epsilon (LR-EP): A variation that balances the advantages of LR-I and LR-P.
  • Pursuit Algorithm: An estimator algorithm that uses past data to estimate reward probabilities and adjusts action probabilities towards the estimated optimal action. This is shown to be faster than LR-I and LR-P.

The core novel contribution is the application of Multiple Models to learning automata. This involves:

  • Multiple Fixed Models: Using a set of pre-defined probability values (models) to estimate the unknown reward probabilities for each action. The agent then selects the best model and adjusts its action probabilities towards the corresponding optimal action.
  • Multiple Adaptive Models: An extension where the models themselves are adaptive, adjusting their estimates based on environmental responses. This is presented as a future direction.

Datasets

Not discussed in the paper. The experiments are simulation-based, using synthetic environments and parameters.

Key Insights and Ideas

  • The "Model" Abstraction: The paper broadens the concept of a "model" beyond a strict system description to anything that aids in decision-making. This allows for flexible application of the multi-model approach.
  • Speedup is Achievable: The core idea is that by using multiple perspectives (models) to estimate the environment's behavior, an agent can gain a more robust and faster understanding of which actions are optimal.
  • Pursuit Algorithm as a Precursor: The pursuit algorithm, which uses past data to estimate reward probabilities, serves as a stepping stone towards the multi-model approach by demonstrating the benefit of using more information than just the immediate response.
  • Generalizability: The authors suggest that the multi-model approach, while demonstrated on simple learning automata, has the potential to be extended to more complex reinforcement learning problems in dynamic environments.

Key Results

The paper presents simulation results demonstrating the effectiveness of the proposed methods:

  • LR-I with 2 actions: Convergence time of approximately 500 steps.
  • LR-I with 10 actions: Convergence time of approximately 2000 steps.
  • LR-P with 2 actions: Probability of the best action reaches 0.95 in 500 steps.
  • Pursuit Algorithm: Significantly faster than LR-I and LR-P. For a 10-action case, convergence is observed around 1500 steps.
  • Multiple Fixed Models: For a 10-action case, convergence time is reduced to approximately 300 steps, a substantial improvement over the 2000 steps for LR-I and 1500 for the pursuit algorithm. This approach also leads to smoother optimal probability convergence.

Limitations and Future Work

  • Limited Scope: The paper focuses on simple learning automata in static environments. The theoretical analysis and practical implementation for more complex dynamic environments (like Markov Decision Processes) are acknowledged as considerably more complex and deferred to future papers.
  • Multiple Adaptive Models: The concept of adaptive multiple models is introduced but not fully explored or simulated in this paper, representing a significant area for future research.
  • Theoretical Rigor: While simulations show promising results, the authors note that the results are not conclusive and more work is needed to fully understand the theoretical underpinnings and guarantees of the multi-model approach in various learning scenarios.
  • Extension to Complex Systems: The authors explicitly state their intention to extend this approach to more complex reinforcement learning schemes in dynamic environments in subsequent publications.

Summary updated

Abstract

This is the first of a series of papers that the authors propose to write on the subject of improving the speed of response of learning systems using multiple models. During the past two decades, the first author has worked on numerous methods for improving the stability, robustness, and performance of adaptive systems using multiple models and the other authors have collaborated with him on some of them. Independently, they have also worked on several learning methods, and have considerable experience with their advantages and limitations. In particular, they are well aware that it is common knowledge that machine learning is in general very slow. Numerous attempts have been made by researchers to improve the speed of convergence of algorithms in different contexts. In view of the success of multiple model based methods in improving the speed of convergence in adaptive systems, the authors believe that the same approach will also prove fruitful in the domain of learning. In this paper, a first attempt is made to use multiple models for improving the speed of response of the simplest learning schemes that have been studied. i.e. Learning Automata.
BibTeX
@misc{narendra2015improving,
  author = {Kumpati S. Narendra and Yu Wang},
  title = {{Improving the Speed of Response of Learning Algorithms Using Multiple Models}},
  year = {2015},
  eprint = {1510.05034},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.05034},
}
Figure