The book gives a systematical presentation of stochastic approximation methods for models of American-type options with general pay-off functions for discrete time Markov price processes. Advanced methods combining backward recurrence algorithms for computing of option rewards and general results on convergence of stochastic space skeleton and tree approximations for option rewards are applied to a variety of models of multivariate modulated Markov price processes. The principal novelty of presented results is based on consideration of multivariate modulated Markov price processes and general pay-off functions, which can depend not only on price but also an additional stochastic modulating index component, and use of minimal conditions of smoothness for transition probabilities and pay-off functions, compactness conditions for log-price processes and rate of growth conditions for pay-off functions. The book also contains an extended bibliography of works in the area. This book is the first volume of the comprehensive two volumes monograph. The second volume will present results on structural studies of optimal stopping domains, Monte Carlo based approximation reward algorithms, and convergence of American-type options for autoregressive and continuous time models, as well as results of the corresponding experimental studies.