The design of absorbing Bayesian pursuit algorithms and the formal analyses of their ε-optimality | Pattern Analysis and Applications Skip to main content
Springer Nature Link
Log in

The design of absorbing Bayesian pursuit algorithms and the formal analyses of their ε-optimality

  • Theoretical Advances
  • Published:
Pattern Analysis and Applications Aims and scope Submit manuscript

Abstract

The fundamental phenomenon that has been used to enhance the convergence speed of learning automata (LA) is that of incorporating the running maximum likelihood (ML) estimates of the action reward probabilities into the probability updating rules for selecting the actions. The frontiers of this field have been recently expanded by replacing the ML estimates with their corresponding Bayesian counterparts that incorporate the properties of the conjugate priors. These constitute the Bayesian pursuit algorithm (BPA), and the discretized Bayesian pursuit algorithm. Although these algorithms have been designed and efficiently implemented, and are, arguably, the fastest and most accurate LA reported in the literature, the proofs of their \(\epsilon\)-optimal convergence has been unsolved. This is precisely the intent of this paper. In this paper, we present a single unifying analysis by which the proofs of both the continuous and discretized schemes are proven. We emphasize that unlike the ML-based pursuit schemes, the Bayesian schemes have to not only consider the estimates themselves but also the distributional forms of their conjugate posteriors and their higher order moments—all of which render the proofs to be particularly challenging. As far as we know, apart from the results themselves, the methodologies of this proof have been unreported in the literature—they are both pioneering and novel.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. In the interest of compactness, unless otherwise stated, we will refer to the CBPA as the BPA.

  2. The version of the BPA presented here, namely the absorbing Bayesian pursuit algorithm (ABPA) is distinct from the version presented in [1]. The reason for this is explained presently.

  3. In the interest of compactness and to avoid repetition, the definition and explanations/statements are given for the ABPA in the main text, and described in a parenthesized manner separately for the DBPA.

  4. We emphasize that proving the convergence in the case of utilizing the corresponding ML estimates is not merely a consequence of the weak law of large numbers. Indeed, one has to also take into consideration the specific details of the LA updating rules using which the actions are chosen for the estimation purposes. The arguments to do this are quite intricate, and they have been presented in fine detail in [29]. This proof is not repeated here, but can be included if requested by the referees.

  5. In the interest of simplicity, at this juncture we have assumed that \(\bar{d}_j\) are independent of each other. We believe that this assumption can be easily relaxed by considering only the individual \(d_j\)’s as in Eq. (5), and not all of them together, as in Eq. (6).

  6. In order to not burden the reader with cumbersome algebraic manipulations, we omit the straightforward steps.

References

  1. Zhang X, Granmo OC, Oommen BJ (2011) The Bayesian pursuit algorithm: a new family of estimator learning automata. In: Proceedings of IEA-AIE 2011. Springer, New York, June 2011, pp 608–620

  2. Zhang X, Granmo O-C, Oommen BJ (2013) On incorporating the paradigms of discretization and Bayesian estimation to create a new family of pursuit learning automata. Appl Intell 39:782–792

    Article  Google Scholar 

  3. Zhang X, Granmo OC, Oommen BJ (2012) Discretized Bayesian pursuit—a new scheme for reinforcement learning. In: Proceedings of IEA-AIE 2012, Dalian, June 2012, pp 784–793

  4. Narendra KS, Thathachar MAL (1974) Learning automata—a survey. IEEE Trans Syst Man Cybern 4:323–334

    Article  MathSciNet  MATH  Google Scholar 

  5. Narendra KS, Thathachar MAL (1989) Learning automata: an introduction. Prentice Hall, New Jersey, USA

  6. Oommen BJ, Agache M (2001) Continuous and discretized pursuit learning schemes: various algorithms and their comparison. IEEE Trans Syst Man Cybern Part B Cybern 31(3):277–287

    Article  Google Scholar 

  7. Oommen BJ, Granmo OC, Pedersen A (2007) Using stochastic AI techniques to achieve unbounded resolution in finite player Goore games and its applications. In: Proceedings of IEEE symposium on computational intelligence and games, Honolulu, April 2007, pp 161–167

  8. Beigy H, Meybodi MR (2000) Adaptation of parameters of BP algorithm using learning automata. In: Proceedings of sixth Brazilian symposium on neural networks, Brazil, November 2000, pp 24–31

  9. Zhang X, Jiao L, Granmo OC, Oommen BJ (2013) Channel selection in cognitive radio networks: a switchable Bayesian learning automata approach. In: Proceedings of PIMRC, London, September 2013, pp 2362–2367

  10. Jiao L, Zhang X, Granmo OC, Oommen BJ (2014) A Bayesian learning automata-based distributed channel selection scheme for cognitive radio networks. In: Proceedings of IEA-AIE, Kaohsiung, June 2014, pp 48–57

  11. Granmo O-C, Oommen BJ, Myrer S-A, Olsen MG (2007) Learning automata-based solutions to the nonlinear fractional knapsack problem with applications to optimal resource allocation. IEEE Trans Syst Man Cybern Part B 37(1):166–175

    Article  Google Scholar 

  12. Granmo OC, Oommen BJ, Myrer SA, Olsen MG (2006) Determining optimal polling frequency using a learning automata-based solution to the fractional knapsack problem. In: Proceedings of the 2006 IEEE international conferences on cybernetics and intelligent systems (CIS) and robotics, automation and mechatronics (RAM), Bangkok, June 2006, pp 1–7

  13. Granmo O-C, Oommen BJ (2011) Learning automata-based solutions to the optimal web polling problem modeled as a nonlinear fractional knapsack problem. Eng Appl Artif Intell 24(7):1238–1251

    Article  Google Scholar 

  14. Granmo OC, Oommen BJ (2006) On allocating limited sampling resources using a learning automata-based solution to the fractional knapsack problem. In: Proceedings of the 2006 international intelligent information processing and web mining conference, advances in soft computing, vol 35, Ustron, June 2006, pp 263–272

  15. Granmo O-C, Oommen BJ (2010) Optimal sampling for estimation with constrained resources using a learning automaton-based solution for the nonlinear fractional knapsack problem. Appl Intell 33(1):3–20

    Article  Google Scholar 

  16. Yazidi A, Granmo O-C, Oommen BJ (2012) Service selection in stochastic environments: a learning-automaton based solution. Appl Intell 36:617–637

    Article  Google Scholar 

  17. Unsal C, Kachroo P, Bay JS (1999) Multiple stochastic learning automata for vehicle path control in an automated highway system. IEEE Trans Syst Man Cybern Part A 29:120–128

    Article  Google Scholar 

  18. Oommen BJ, Roberts TD (2000) Continuous learning automata solutions to the capacity assignment problem. IEEE Trans Comput 49:608–620

    Article  Google Scholar 

  19. Oommen BJ, Croix TDS (1997) String taxonomy using learning automata. IEEE Trans Syst Man Cybern 27:354–365

    Article  Google Scholar 

  20. Oommen BJ, Croix TDS (1996) Graph partitioning using learning automata. IEEE Trans Comput 45:195–208

    Article  MathSciNet  MATH  Google Scholar 

  21. Dean T, Angluin D, Basye K, Engelson S, Aelbling L, Maron O (1995) Inferring finite automata with stochastic output functions and an application to map learning. Mach Learn 18:81–108

    Google Scholar 

  22. Thathachar MAL, Sastry PS (1986) Estimator algorithms for learning automata. In: Proceedings of the platinum jubilee conference on systems and signal processing, Bangalore, December 1986, pp 29–32

  23. Oommen BJ, Lanctôt JK (1990) Discretized pursuit learning automata. IEEE Trans Syst Man Cybern 20:931–938

    Article  MathSciNet  MATH  Google Scholar 

  24. Lanctôt JK, Oommen BJ (1992) Discretized estimator learning automata. IEEE Trans Syst Man Cybern Part B Cybern 22(6):1473–1483

    Article  MathSciNet  MATH  Google Scholar 

  25. Lanctôt JK, Oommen BJ (1991) On discretizing estimator-based learning algorithms. IEEE Trans Syst Man Cybern Part B Cybern 2:1417–1422

    Google Scholar 

  26. Rajaraman K, Sastry PS (1996) Finite time analysis of the pursuit algorithm for learning automata. IEEE Trans Syst Man Cybern Part B Cybern 26:590–598

    Article  Google Scholar 

  27. Martin R, Omkar T (2012) On \(\epsilon\)-optimality of the pursuit learning algorithm. J Appl Probab 49(3):795–805

    Article  MathSciNet  MATH  Google Scholar 

  28. Zhang X, Granmo OC, Oommen BJ, Jiao L (2013) On using the theory of regular functions to prove the \(\epsilon\)-optimality of the continuous pursuit learning automaton. In: Proceedings of IEA-AIE 2013. Springer, Amsterdan, June 2013, pp 262–271

  29. Zhang X, Granmo O-C, Oommen BJ, Jiao L (2014) A formal proof of the \(\epsilon\)-optimality of absorbing continuous pursuit algorithms using the theory of regular functions. Appl Intell 41:974–985

    Article  Google Scholar 

  30. Zhang X, Oommen BJ, Granmo OC, Jiao L (2014) Using the theory of regular functions to formally prove the \(\epsilon\)-optimality of discretized pursuit learning algorithms. In: Proceedings of IEA-AIE. Kaohsiung. Springer, June 2014, pp 379–388

  31. Zhang X, Oommen BJ, Granmo OC, Jiao L (2014) A formal proof of the \(\epsilon\)-optimality of discretized pursuit algorithms. Appl Intell

  32. Oommen BJ (1986) Absorbing and ergodic discretized two-action learning automata. IEEE Trans Syst Man Cybern 16:282–296

    Article  MathSciNet  MATH  Google Scholar 

  33. Lanctôt JK, Oommen BJ (1992) Discretized estimator learning automata. IEEE Trans Syst Man Cybern 22(6):1473–1483

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of ICT, University of Agder, Grimstad, Norway

    Xuan Zhang, B. John Oommen & Ole-Christoffer Granmo

  2. School of Computer Science, Carleton University, Ottawa, K1S 5B6, Canada

    B. John Oommen

Authors
  1. Xuan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. John Oommen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ole-Christoffer Granmo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to B. John Oommen.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, X., Oommen, B.J. & Granmo, OC. The design of absorbing Bayesian pursuit algorithms and the formal analyses of their ε-optimality. Pattern Anal Applic 20, 797–808 (2017). https://doi.org/10.1007/s10044-016-0535-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10044-016-0535-1

Keywords

Search

Navigation