Accession Number:

ADA243074

Title:

Computing Approximate Solutions to Markov Renewal Programs with Continuous State Spaces

Descriptive Note:

Research rept.

Corporate Author:

LAVAL UNIV QUEBEC DEPT D'INFORMATIQUE

Personal Author(s):

• L'Ecuyer, Pierre

Report Date:

1989-09-01

Pagination or Media Count:

32.0

Abstract:

Value iteration and policy iteration are two well known computational methods for solving Markov renewal decision processes. Value iteration converges linearly, while policy iteration typically converges quadratically and is therefore more attractive in principle. However, when the state space is very large or continuous, the latter asks for solving at each iteration a large linear system or integral equation and becomes unpractical. We propose an approximate policy iteration method, targeted especially to systems with continuous or large state spaces, for which the Bellman expected cost-to-go function is relatively smooth or piecewise smooth. These systems occur quite frequently in practice. The method is based on an approximation of the Bellman function by a linear combination of an a priori fixed set of base functions. At each policy iteration, we build a linear system in terms of the coefficients of these base functions, and solve this system approximately. We give special attention to a particular case of finite element approximation where the Bellman function is expressed directly as a convex combination of its values at a finite set of grid points.

Descriptors:

• *LINEAR SYSTEMS
• POLICIES
• FINITE ELEMENT ANALYSIS
• GRIDS(COORDINATES)
• SET THEORY
• COEFFICIENTS
• NUMERICAL METHODS AND PROCEDURES
• INTEGRAL EQUATIONS
• ITERATIONS
• FUNCTIONS
• SOLUTIONS(GENERAL)

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE