Stochastic Approximation Algorithms and Applications

Introduction1 Review of Continuous Time Models1.1 Martingales and Martingale Inequalities1.2 Stochastic Integration1.3 Stochastic Differential Equations: Diffusions1.4 Reflected Diffusions1.5 Processes with Jumps2 Controlled Markov Chains2.1 Recursive Equations for the Cost2.2 Optimal Stopping Problems2.3 Discounted Cost2.4 Control to a Target Set and Contraction Mappings2.5 Finite Time Control Problems3 Dynamic Programming Equations3.1 Functionals of Uncontrolled Processes3.2 The Optimal Stopping Problem3.3 Control Until a Target Set Is Reached3.4 A Discounted Problem with a Target Set and Reflection3.5 Average Cost Per Unit Time4 Markov Chain Approximation Method: Introduction4.1 Markov Chain Approximation4.2 Continuous Time Interpolation4.3 A Markov Chain Interpolation4.4 A Random Walk Approximation4.5 A Deterministic Discounted Problem4.6 Deterministic Relaxed Controls5 Construction of the Approximating Markov Chains5.1 One Dimensional Examples5.2 Numerical Simplifications5.3 The General Finite Difference Method5.4 A Direct Construction5.5 Variable Grids5.6 Jump Diffusion Processes5.7 Reflecting Boundaries5.8 Dynamic Programming Equations5.9 Controlled and State Dependent Variance6 Computational Methods for Controlled Markov Chains6.1 The Problem Formulation6.2 Classical Iterative Methods6.3 Error Bounds6.4 Accelerated Jacobi and Gauss-Seidel Methods6.5 Domain Decomposition6.6 Coarse Grid-Fine Grid Solutions6.7 A Multigrid Method6.8 Linear Programming7 The Ergodic Cost Problem: Formulation and Algorithms7.1 Formulation of the Control Problem7.2 A Jacobi Type Iteration7.3 Approximation in Policy Space7.4 Numerical Methods7.5 The Control Problem7.6 The Interpolated Process7.7 Computations7.8 Boundary Costs and Controls8 Heavy Traffic and Singular Control8.1 Motivating Examples&nb