IEEE Transactions on Automatic Control · 2002 · 69 citations · 25 references
ComputingComputer ScienceAlgorithmsMachine LearningMarkov Decision ProcessesApproximation AlgorithmsOptimal ControlReinforcement LearningStochastic ControlApproximate Dynamic ProgrammingAverage Cost FunctionsKernel Value Function ApproximationState Transition ProbabilitiesState-value FunctionTransition ProbabilitiesValue Function Estimation
Reinforcement learning (RL) is concerned with the identification of optimal controls in Markov decision processes (MDPs) where no explicit model of the transition probabilities is available. We propose a class of RL algorithms which always produces stable estimates of the value function. In detail, we use "local averaging" methods to construct an approximate dynamic programming (ADP) algorithm. Nearest-neighbor regression, grid-based approximations, and trees can all be used as the basis of this approximation. We provide a thorough theoretical analysis of this approach and we demonstrate that ADP converges to a unique approximation in continuous-state average-cost MDPs. In addition, we prove that our method is consistent in the sense that an optimal approximate strategy is identified asymptotically. With regard to a practical implementation, we suggest a reduction of ADP to standard dynamic programming in an artificial finite-state MDP.
25
Classification and Regression Trees.
Alexander Gordon, Leo Breiman, Jerome H. Friedman et al. · Biometrics · 1984 · 23.9K citations
Classification and Regression Trees.
John Van Ryzin, Leo Breiman, Jerome H. Friedman et al. · Journal of the American Statistical Association · 1986 · 21K citations
Learning to Predict by the Methods of Temporal Differences
Richard S. Sutton · Machine Learning · 1988 · 4K citations · Full text
É. A. Nadaraya · Theory of Probability and Its Applications · 1964 · 3.4K citations