Using randomization to break the curse of dimensionality.

This paper introduces random versions of successive approximations and multigrid algorithms for computing approximate solutions to a class of finite and infinite horizon Markovian decision problems (MDPs). We prove that these algorithms succeed in breaking the “curse of dimensionality” for a subcla...

Descripción completa

Detalles Bibliográficos
Publicado en:	Econometrica Vol. 65; pp. 487 - 517
Autor principal:	Rust, John
Formato:	Artículo
Publicado:	Wiley-Blackwell May 1997
Materias:	Markov processes Mathematical models of decision making Dynamic programming
Acceso en línea:	Ver este registro en EBSCOhost

Descripción
Sumario:	This paper introduces random versions of successive approximations and multigrid algorithms for computing approximate solutions to a class of finite and infinite horizon Markovian decision problems (MDPs). We prove that these algorithms succeed in breaking the “curse of dimensionality” for a subclass of MDPs known as discrete decision processes (DDPs). Reprinted by permission of the Econometric Society.