内容简介：
This revised and expanded second edition presents a thorough development of the modern theory of stochastic approximation or recursive stochastic algorithms for both constrained and unconstrained problems. There is a complete development of both probability one and weak convergence methods for very general noise processes. The proofs of convergence use the ODE method, the most powerful to date. The assumptions and proof methods are designed to cover the needs of recent applications. The development proceeds from simple to complex problems, allowing the underlying ideas to be more easily understood. Rate of convergence, iterate averaging, high-dimensional problems, stability-ODE methods, two time scale, asynchronous and decentralized algorithms, state-dependent noise, stability methods for correlated noise, perturbed test function methods, and large deviations methods are covered. Many motivating examples from learning theory, ergodic cost problems for discrete event systems, wireless communications, adaptive control, signal processing, and elsewhere illustrate the applications of the theory.
英文目录：
Preface and Introduction
1 Introduction: Applications and Issues
1.0 Outline of Chapter
1.1 The Robbins–Monro Algorithm
1.1.1 Introduction
1.1.2 Finding the Zeros of an Unknown Function
1.1.3 Best Linear Least Squares Fit
1.1.4 Minimization by Recursive Monte Carlo
1.2 The Kiefer–Wolfowitz Procedure
1.2.1 The Basic Procedure
1.2.2 Random Directions
1.3 Extensions of the Algorithms
1.3.1 A Variance Reduction Method
1.3.2 Constraints
1.3.3 Averaging of the Iterates: “Polyak Averaging”
1.3.4 Averaging the Observations
1.3.5 Robust Algorithms
1.3.6 Nonexistence of the Derivative at Some θ
1.3.7 Convex Optimization and Subgradients
1.4 A Lagrangian Algorithm for Constrained Function Minimization
2 Applications
2.0 Outline of Chapter
2.1 An Animal Learning Model
2.2 A Neural Network
2.3 State-Dependent Noise
2.4 Learning Optimal Controls
2.4.1 Q-Learning
2.4.2 Approximating a Value Function
2.4.3 Parametric Optimization of a Markov Chain Control Problem
2.5 Optimization of a GI/G/1 Queue
2.5.1 Derivative Estimation and Infinitesimal Perturbation Analysis: A Brief Review
2.5.2 The Derivative Estimate for the Queueing Problem
2.6 Passive Stochastic Approximation
2.7 Learning in Repeated Stochastic Games
3 Signal Processing, Communications, and Control
3.0 Outline of Chapter
3.1 Parameter Identification and Tracking
3.1.1 The Classical Model
3.1.2 ARMA and ARMAX Models
3.2 Tracking Time Varying Systems
3.2.1 The Algorithm
3.2.2 Some Data
3.3 Feedback and Averaging
3.4 Applications in Communications Theory
3.4.1 Adaptive Noise Cancellation and Disturbance Rejection
3.4.2 Adaptive Equalizers
3.4.3 An ARMA Model, with a Training Sequence
3.5 Adaptive Antennas and Mobile Communications
3.6 Proportional Fair Sharing
4 Mathematical Background
4.0 Outline of Chapter
4.1 Martingales and Inequalities
4.2 Ordinary Differential Equations
4.2.1 Limits of a Sequence of Continuous Functions
4.2.2 Stability of Ordinary Differential Equations
4.3 Projected ODE
4.4 Cooperative Systems and Chain Recurrence
4.4.1 Cooperative Systems
4.4.2 Chain Recurrence
4.5 Stochastic Stability
5 Convergence w.p.1: Martingale Difference Noise
5.0 Outline of Chapter
5.1 Truncated Algorithms: Introduction
5.2 The ODE Method
5.2.1 Assumptions and the Main Convergence Theorem
5.2.2 Convergence to Chain Recurrent Points
5.3 A General Compactness Method
5.3.1 The Basic Convergence Theorem
5.3.2 Suffcient Conditions for the Rate of Change Condition
5.3.3 The Kiefer–Wolfowitz Algorithm
5.4 Stability and Combined Stability–ODE Methods
5.4.1 A Liapunov Function Method for Convergence
5.4.2 Combined Stability–ODE Methods
5.5 Soft Constraints
5.6 Random Directions, Subgradients, and Differential Inclusions
5.7 Animal Learning and Pattern Classification
5.7.1 The Animal Learning Problem
5.7.2 The Pattern Classification Problem
5.8 Non-Convergence to Unstable Points
6 Convergence w.p.1: Correlated Noise
6.0 Outline of Chapter
6.1 A General Compactness Method
6.1.1 Introduction and General Assumptions
6.1.2 The Basic Convergence Theorem
6.1.3 Local Convergence Results
6.2 Suffcient Conditions
6.3 Perturbed State Criteria
6.3.1 Perturbed Iterates
6.3.2 General Conditions for the Asymptotic Rate of Change
6.3.3 Alternative Perturbations
6.4 Examples of State Perturbation
6.5 Kiefer–Wolfowitz Algorithms
6.6 State-Dependent Noise
6.7 Stability-ODE Methods
6.8 Differential Inclusions
6.9 Bounds on Escape Probabilities
6.10 Large Deviations
6.10.1 Two-Sided Estimates
6.10.2 Upper Bounds
6.10.3 Bounds on Escape Times
7 Weak Convergence: Introduction
7.0 Outline of Chapter
7.1 Introduction
7.2 Martingale Difference Noise
7.3 Weak Convergence
7.3.1 Definitions
7.3.2 Basic Convergence Theorems
7.4 Martingale Limits
7.4.1 Verifying that a Process Is a Martingale
7.4.2 The Wiener Process
7.4.3 Perturbed Test Functions
8 Weak Convergence Methods for General Algorithms
8.0 Outline of Chapter
8.1 Exogenous Noise
8.2 Convergence: Exogenous Noise
8.2.1 Constant Step Size: Martingale Difference Noise
8.2.2 Correlated Noise
8.2.3 Step Size
8.2.4 Random
8.2.5 Differential Inclusions
8.2.6 Time-Dependent ODEs
8.3 The Kiefer–Wolfowitz Algorithm
8.3.1 Martingale Difference Noise
8.3.2 Correlated Noise
8.4 State-Dependent Noise
8.4.1 Constant Step Size
8.4.2 Decreasing Step Size
8.4.3 The Invariant Measure Method
8.4.4 General Forms of the Conditions
8.4.5 Observations Depending on the Past of the Iterate Sequence or
Working Directly with
8.5 Unconstrained Algorithms and the ODE-Stability Method
8.6 Two-Time-Scale Problems
8.6.1 The Constrained Algorithm
8.6.2 Unconstrained Algorithms: Stability
9 Applications: Proofs of Convergence
9.0 Outline of Chapter
9.1 Introduction
9.1.1 General Comments
9.1.2 A Simple Illustrative SDE Example
9.2 A SDE Example
9.3 A Discrete Example: A GI/G/1 Queue
9.4 Signal Processing Problems
9.5 Proportional Fair Sharing
10 Rate of Convergence
10.0 Outline of Chapter
10.1 Exogenous Noise: Constant Step Size
10.1.1 Martingale Difference Noise
10.1.2 Correlated Noise
10.2 Exogenous Noise: Decreasing Step Size
10.2.1 Martingale Difference Noise
10.2.2 Optimal Step Size Sequence
10.2.3 Correlated Noise
10.3 Kiefer–Wolfowitz Algorithm
10.3.1 Martingale Difference Noise
10.3.2 Correlated Noise
10.4 Tightness: W.P.1 Convergence
10.4.1 Martingale Difference Noise: Robbins–Monro Algorithm
10.4.2 Correlated Noise
10.4.3 Kiefer–Wolfowitz Algorithm
10.5 Tightness: Weak Convergence
10.5.1 Unconstrained Algorithm
10.5.2 Local Methods for Proving Tightness
10.6 Weak Convergence to a Wiener Process
10.7 Random Directions
10.7.1 Comparison of Algorithms
10.8 State-Dependent Noise
10.9 Limit Point on the Boundary
11 Averaging of the Iterates
11.0 Outline of Chapter
11.1 Minimal Window of Averaging
11.1.1 Robbins–Monro Algorithm: Decreasing Step Size
11.1.2 Constant Step Size
11.1.3 Averaging with Feedback and Constant Step Size
11.1.4 Kiefer–Wolfowitz Algorithm
11.2 A Two-Time-Scale Interpretation
11.3 Maximal Window of Averaging
11.4 The Parameter Identification Problem
12 Distributed/Decentralized and Asynchronous Algorithms
12.0 Outline of Chapter
12.1 Examples
12.1.1 Introductory Comments
12.1.2 Pipelined Computations
12.1.3 A Distributed and Decentralized Network Model
12.1.4 Multiaccess Communications
12.2 Real-Time Scale: Introduction
12.3 The Basic Algorithms
12.3.1 Constant Step Size: Introduction
12.3.2 Martingale Difference Noise
12.3.3 Correlated Noise
12.3.4 Analysis for and
12.4 Decreasing Step Size
12.5 State-Dependent Noise
12.6 Rate of Convergence
12.7 Stability and Tightness of the Normalized Iterates
12.7.1 Unconstrained Algorithms
12.8 Convergence for Q-Learning: Discounted Cost
References
Symbol Index
Subject Index
