Learning and value function approximation in complex decision processes
In principle, a wide variety of sequential decision problems--ranging from dynamic resource allocation in telecommunication networks to financial risk management--can be formulated in terms of stochastic control and solved by the algorithms of dynamic programming. Such algorithms compute and store a value function, which evaluates expected future reward as a function of current state. Unfortunately, exact computation of the value function typically requires time and storage that grow proportionately with the number of states, and consequently, the enormous state spaces that arise in practical applications render the algorithms intractable. 
In this thesis, we study tractable methods that approximate the value function. Our work builds on research in an area of artificial intelligence known as reinforcement learning. A point of focus of this thesis is temporal-difference learning--a stochastic algorithm inspired to some extent by phenomena observed in animal behavior. Given a selection of basis functions, the algorithm updates weights during simulation of the system such that the weighted combination of basis functions ultimately approximates a value function. We provide an analysis (a proof of convergence, together with bounds on approximation error) of temporal-difference learning in the context of autonomous (uncontrolled) systems as applied to the approximation of (1) infinite horizon discounted rewards and (2) average and differential rewards. 
As a special case of temporal-difference learning in a context involving control, we propose variants of the algorithm that generate approximate solutions to optimal stopping problems. We analyze algorithms designed for several problem classes: (1) optimal stopping of a stationary mixing process with an infinite horizon and discounted rewards; (2) optimal stopping of an independent increments process with an infinite horizon and discounted rewards; (3) optimal stopping with a finite horizon and discounted rewards; (4) a zero-sum two-player stopping game with an infinite horizon and discounted rewards. We also present a computational case study involving a complex optimal stopping problem that is representative of those arising in the financial derivatives industry. 
In addition to algorithms for tuning basis function weights, we study an approach to basis function generation. In particular, we explore the use of "scenarios" that are representative of the range of possible events in a system. Each scenario is used to construct a basis function that maps states to future rewards contingent on the future realization of the scenario. We derive, in the context of autonomous systems, a bound on the number of "representative scenarios" that suffices for uniformly accurate approximation of the value function. The bound exhibits a dependence on a measure of "complexity" of the system that can often grow at a rate much slower that the state space size. (Copies available exclusively from MIT Libraries Rm. 14-0551, Cambridge, MA 02139-4307 Ph. 617-253-5668; Fax 617-253-1690.)