A Cultural Algorithm for POMDPs from Stochastic Inventory Control

S. Prestwich, S.A. Tarim, R. Rossi, B. Hnich

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

3 Citations (Scopus)

Abstract

Reinforcement Learning algorithms such as SARSA with an eligibility trace, and Evolutionary Computation methods such as genetic algorithms, are competing approaches to solving Partially Observable Markov Decision Processes (POMDPs) which occur in many fields of Artificial Intelligence. A powerful form of evolutionary algorithm that has not previously been applied to POMDPs is the cultural algorithm, in which evolving agents share knowledge in a belief space that is used to guide their evolution. We describe a cultural algorithm for POMDPs that hybridises SARSA with a noisy genetic algorithm, and inherits the latter¿s convergence properties. Its belief space is a common set of state-action values that are updated during genetic exploration, and conversely used to modify chromosomes. We use it to solve problems from stochastic inventory control by finding memoryless policies for nondeterministic POMDPs. Neither SARSA nor the genetic algorithm dominates the other on these problems, but the cultural algorithm outperforms the genetic algorithm, and on highly non-Markovian instances also outperforms SARSA
Original languageEnglish
Title of host publicationHybrid Metaheuristics
EditorsM.J. Blesa Aguilera, C. Blum, C. Cotta, A.J. Fernández Leiva, J.E. Gallardo Ruiz, M. Sampels
Pages16-28
DOIs
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin/Heidelberg
Number5296

Fingerprint Dive into the research topics of 'A Cultural Algorithm for POMDPs from Stochastic Inventory Control'. Together they form a unique fingerprint.

Cite this