title: Amoeba-inspired Tug-of-War algorithms for exploration-exploitation dilemma in extended Bandit Problem.
abstract: The true slime mold Physarum polycephalum, a single-celled amoeboid organism, is capable of efficiently allocating a constant amount of intracellular resource to its pseudopod-like branches that best fit the environment where dynamic light stimuli are applied. Inspired by the resource allocation process, the authors formulated a concurrent search algorithm, called the Tug-of-War (TOW) model, for maximizing the profit in the multi-armed Bandit Problem (BP). A player (gambler) of the BP should decide as quickly and accurately as possible which slot machine to invest in out of the N machines and faces an "exploration-exploitation dilemma." The dilemma is a trade-off between the speed and accuracy of the decision making that are conflicted objectives. The TOW model maintains a constant intracellular resource volume while collecting environmental information by concurrently expanding and shrinking its branches. The conservation law entails a nonlocal correlation among the branches, i.e., volume increment in one branch is immediately compensated by volume decrement(s) in the other branch(es). Owing to this nonlocal correlation, the TOW model can efficiently manage the dilemma. In this study, we extend the TOW model to apply it to a stretched variant of BP, the Extended Bandit Problem (EBP), which is a problem of selecting the best M-tuple of the N machines. We demonstrate that the extended TOW model exhibits better performances for 2-tuple-3-machine and 2-tuple-4-machine instances of EBP compared with the extended versions of well-known algorithms for BP, the ϵ-Greedy and SoftMax algorithms, particularly in terms of its short-term decision-making capability that is essential for the survival of the amoeba in a hostile environment.
authors.affiliation: Earth-Life Science Institute, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan; PRESTO, Japan Science and Technology Agency, 4-1-8 Honcho, Kawaguchi-shi, Saitama 332-0012, Japan. Electronic address: masashi.aono@elsi.jp.
authors.forename: Masashi
authors.initials: M
authors.lastname: Aono
authors.affiliation: WPI Center for Materials Nanoarchitectonics (MANA), National Institute for Materials Science (NIMS), 1-1 Namiki, Tsukuba, Ibaraki 305-0044, Japan.
authors.forename: Song-Ju
authors.initials: SJ
authors.lastname: Kim
authors.affiliation: Department of Electronic Chemistry, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, Yokohama 226-8503, Japan.
authors.forename: Masahiko
authors.initials: M
authors.lastname: Hara
authors.affiliation: Computer and Information Science Department, Cleveland State University, Cleveland, OH 44115, USA.
authors.forename: Toshinori
authors.initials: T
authors.lastname: Munakata
mesh_terms: D000465:Algorithms; D000818:Animals; D032701:Biomimetics / Q000379:methods*; D048429:Cell Size; D003198:Computer Simulation; D003657:Decision Making / Q000502:physiology*; D003661:Decision Support Techniques; D005106:Exploratory Behavior / Q000502:physiology*; D005715:Gambling; D005716:Game Theory; D008954:Models, Biological; D016839:Physarum polycephalum / Q000166:cytology* / Q000502:physiology*; D011235:Predatory Behavior / Q000502:physiology
keywords: Decision making; Multi-armed Bandit Problem; Natural computing; Physarum polycephalum; Resource allocation