Evolutionary Policy Iteration for Solving Markov Decision Processes

Abstract

The authors propose a novel algorithm called Evolutionary Policy Iteration (EPI) for solving infinite horizon discounted reward Markov Decision Process (MDP) problems. EPI inherits the spirit of the well-known PI algorithm, but eliminates the need to maximize over the entire action space in the policy improvement step, so it should be most effective for problems with very large action spaces. EPI iteratively generates a "population" or a set of policies such that the performance of the "elite policy" for a population is monotonically improved with respect to a defined fitness function. EPI converges with probability one to a population whose elite policy is an optimal policy for a given MDP. EPI is naturally parallelizable, and along this discussion a distributed variant of PI also is studied.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 16, 2002
Accession Number
ADA451998

Entities

People

  • Hong-gi Lee
  • Hyeong S. Chang
  • Michael C. Fu
  • Steven I Marcus

Organizations

  • University of Maryland

Tags

Communities of Interest

  • C4I
  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Adaptive Systems
  • Algorithms
  • Computations
  • Convergence
  • Demographic Cohorts
  • Dynamic Programming
  • Electrical Engineering
  • Engineering
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Iterations
  • Mutations
  • Probability
  • Probability Distributions
  • Random Variables
  • Switching
  • Universities

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Strategic Security Studies
  • Systems Analysis and Design

Technology Areas

  • Space