Title
Preface
Contents
Part I Introduction to Stochastic Recursive
Algorithms
Introduction
Introduction
Overview of the Remaining Chapters
Concluding Remarks
References
Deterministic Algorithms for Local Search
Introduction
Deterministic Algorithms for Local Search
References
Stochastic Approximation Algorithms
Introduction
The Robbins-Monro Algorithm
Convergence of the Robbins-Monro Algorithm
Multi-timescale Stochastic Approximation
Convergence of the Multi-timescale Algorithm
Concluding Remarks
References
Part II
Gradient Estimation Schemes
Kiefer-Wolfowitz Algorithm
Introduction
The Basic Algorithm
Extension to Multi-dimensional Parameter
Variants of the Kiefer-Wolfowitz Algorithm
Fixed Perturbation Parameter
One-Sided Variants
Concluding Remarks
References
Gradient Schemes with Simultaneous
Perturbation Stochastic Approximation
Introduction
The Basic SPSA Algorithm
Gradient Estimate Using Simultaneous Perturbation
The Algorithm
Convergence Analysis
Variants of the Basic SPSA Algorithm
One-Measurement SPSA Algorithm
One-Sided SPSA Algorithm
Fixed Perturbation Parameter
General Remarks on SPSA Algorithms
SPSA Algorithms with Deterministic Perturbations
Properties of Deterministic Perturbation Sequences
Hadamard Matrix Based Construction
Two-Sided SPSA with Hadamard Matrix Perturbations
One-Sided SPSA with Hadamard Matrix Perturbations
One-Measurement SPSA with Hadamard Matrix Perturbations
SPSA Algorithms for Long-Run Average Cost Objective
The Framework
The Two-Simulation SPSA Algorithm
Assumptions
Convergence Analysis
Projected SPSA Algorithm
Concluding Remarks
References
Smoothed Functional Gradient Schemes
Introduction
Gaussian Based SF Algorithm
Gradient Estimation via Smoothing
The Basic Gaussian SF Algorithm
Convergence Analysis of Gaussian SF Algorithm
Two-Measurement Gaussian SF Algorithm
General Conditions for a Candidate Smoothing Function
Cauchy Variant of the SF Algorithm
Gradient Estimate
Cauchy SF Algorithm
SF Algorithms for the Long-Run Average Cost Objective
The G-SF1 Algorithm
The G-SF2 Algorithm
Projected SF Algorithms
Concluding Remarks
References
Part III
Hessian Estimation Schemes
Newton-Based Simultaneous Perturbation
Stochastic Approximation
Introduction
The Framework
Newton SPSA Algorithms
Four-Simulation Newton SPSA (N-SPSA4)
Three-Simulation Newton SPSA (N-SPSA3)
Two-Simulation Newton SPSA (N-SPSA2)
One-Simulation Newton SPSA (N-SPSA1)
Woodbury's Identity Based Newton SPSA Algorithms
Convergence Analysis
Assumptions
Convergence Analysis of N-SPSA4
Convergence Analysis of N-SPSA3
Convergence Analysis of N-SPSA2
Convergence Analysis of N-SPSA1
Convergence Analysis of W-SPSA Algorithms
Concluding Remarks
References
Newton-Based Smoothed Functional Algorithms
Introduction
The Hessian Estimates
One-Simulation Hessian SF Estimate
Two-Simulation Hessian SF Estimate
The Newton SF Algorithms
The One-Simulation Newton SF Algorithm (N-SF1)
The Two-Simulation Newton SF Algorithm (N-SF2)
Convergence Analysis of Newton SF Algorithms
Convergence of N-SF1
Convergence of N-SF2
Concluding Remarks
References
Part IV
Variations to the Basic Scheme
Discrete Parameter Optimization
Introduction
The Framework
The Deterministic Projection Operator
The Random Projection Operator
A Generalized Projection Operator
Regular Projection Operator to
Basic Results for the Generalized Projection Operator Case
The Algorithms
The SPSA Algorithm
The SFA Algorithm
Convergence Analysis
Concluding Remarks
References
Algorithms for Constrained Optimization
Introduction
The Framework
Algorithms
Constrained Gradient-Based SPSA Algorithm (CG-SPSA)
Constrained Newton-Based SPSA Algorithm (CN-SPSA)
Constrained Gradient-Based SF Algorithm (CG-SF)
Constrained Newton-Based SF Algorithm (CN-SF)
A Sketch of the Convergence
Concluding Remarks
References
Reinforcement Learning
Introduction
Markov Decision Processes
Numerical Procedures for MDPs
Numerical Procedures for Discounted Cost MDPs
Numerical Procedures for Long-Run Average Cost MDPs
Reinforcement Learning Algorithms for Look-up Table Case
An Actor-Critic Algorithm for Infinite Horizon Discounted Cost MDPs
The Q-Learning Algorithm and a Simultaneous Perturbation Variant for Infinite Horizon Discounted Cost MDPs
Actor-Critic Algorithms for Long-Run Average Cost MDPs
Reinforcement Learning Algorithms with Function Approximation
Temporal Difference (TD) Learning with Discounted Cost
An Actor-Critic Algorithm with a Temporal Difference Critic for Discounted Cost MDPs
Function Approximation Based Q-Learning Algorithm and a Simultaneous Perturbation Variant for Infinite Horizon Discounted Cost MDPs
Concluding Remarks
References
Part V
Applications
Service Systems
Introduction
Service System Framework
Problem Formulation
Solution Methodology
First Order Methods
SASOC-SPSA
SASOC-SF-N
SASOC-SF-C
Second Order Methods
SASOC-H
SASOC-W
Notes on Convergence
Summary of Experiments
Concluding Remarks
References
Road Traffic Control
Introduction
Q-Learning for Traffic Light Control
Traffic Control Problem as an MDP
The TLC Algorithm
Summary of Experimental Results
Threshold Tuning Using SPSA
The Threshold Tuning Algorithm
Traffic Light Control with Threshold Tuning
Summary of Experimental Results
Concluding Remarks
References
Communication Networks
Introduction
The Random Early Detection (RED) Scheme for the Internet
Introduction to RED Flow Control
The Framework
The B-RED and P-RED Stochastic Approximation Algorithms
Summary of Experimental Results
Optimal Policies for the Retransmission Probabilities in Slotted Aloha
Introduction to the Slotted Aloha Multiaccess Communication Protocol
The SDE Framework
The Algorithm
Summary of Experimental Results
Dynamic Multi-layered Pricing Schemes for the Internet
Introduction to Dynamic Pricing Schemes
The Pricing Framework
The Price Feed-Back Policies and the Algorithms
Summary of Experimental Results
Concluding Remarks
References
Part VI
Appendix
Convergence Notions for a Sequence of Random Vectors
Reference
Martingales
References
Ordinary Differential Equations
References
The Borkar-Meyn Theorem for Stability and Convergence
References
The Kushner-Clark Theorem for Convergence
References
Index