Monte Carlo Method
The Monte Carlo method, used to investigate a wide variety of problems, is a stochastic technique based on the statistics of random events applied to large numbers. Monte Carlo methods use random numbers and probability statistics to explain a variety of phenomena. Although there are several types of Monte Carlo methods the simplest is the hit-and-miss integration method and is the one most often employed. Monte Carlo methods require only experience and this differentiates it from other stochastic methods because it requires no prior knowledge of the environment's dynamics, yet can still attain optimal behavior. This method is useful for obtaining solutions to problems that are too complicated to solve analytically. There are two types of Monte Carlo methods: the simple Monte Carlo method and the sophisticated Monte Carlo method. The first, simple Monte Carlo method, is a direct modeling of a random process. The second type, sophisticated Monte Carlo method, recasts deterministic problems in probabilistic terms.
By averaging sample returns the Monte Carlo methods provide ways to solve the reinforcement learning problem. Because of this Monte Carlo methods are described for episodic tasks only. That is, experience is divided into episodes and all episodes eventually terminate no matter what outcome may be. So rather than be incremental in a step by step fashion Monte Carlo methods require that the action is incremental in an episode by episode sense. It is a method based on determining results based on averaging complete returns rather than learning from partial returns. The Monte Carlo method is one of the most powerful techniques available in terms of the application to such a wide range of problems.
All Monte Carlo methods are comprised of several different major components. The physical or mathematical system must be described by a set of probability distribution functions. These functions enable the investigator to determine if a positive or negative result will occur for a particular input. A source of random numbers uniformly distributed on the interval of interest is required. A sampling rule that describes a prescription for sampling from the probability distribution functions on the interval of interest must be given. The outcome, whether it is positive or negative, must be accumulated and tallied. The variance as a function of the number of trials must be determined and a variance reduction technique must be available to reduce the computational time for the Monte Carlo simulation. Lastly, algorithms that allow Monte Carlo methods to be implemented on advanced computer systems can be helpful in analyzing the data.
As an example we will use the popular hit-and-miss integration method to calculate the value of . If we draw a circle in a square and shade inside of the circle and imagine that we are throwing darts randomly at the figure that sometimes the darts hit inside of the square and sometimes inside of the circle. It should be apparent that of the total number of darts that hit within the square, the number of darts that hit within the shaded circle will be proportional to the area of the circle so that: (# of darts hitting shaded circle)/(# of darts hitting inside square) = (area of circle)/(area of square). From geometry we know that: (# of darts hitting shaded circle)/(# of darts hitting inside square) = (r2)/r2) = . If each dart that is thrown lands inside of the square then the ratio of dart hits in the shaded circle to throws will be equal to the value of . In reality it actually takes a very large number of throws to get a decent value of but there are methods to reduce the number of attempts and get a better estimate.
The Monte Carlo method is named after the city in the Monaco principality known for gambling. More precisely S. Ulam named it in 1946 after a roulette wheel, which is a simple random number generator. S. Ulam had a relative that had a propensity to gamble and so he named the method in the relative's honor. The well formulated methods date back to the second world war when it was first employed during the Manhattan Project, where very complex equations had to be solved that could not be approached using traditional methods. There are however a number of isolated instances on much earlier occasions where similar methods were employed. In a paper of 1873 A. Hall describes an experimental determination of which used methods similar to Monte Carlo methods. In 1899 Lord Rayleigh showed that without absorbing barriers a one-dimensional random walk could provide an approximate solution to a parabolic differential equation. Later, in 1931, Kolmogorov demonstrated a relationship between Markov stochastic processes and certain intergro-differential equations. Although crude Monte Carlo methods were employed in studies that predate that of the development of the atomic bomb the systematic development of Monte Carlo ideas emerged in 1948 when a group of scientists obtained Monte Carlo estimates for the eigenvalues of the Schrödinger equation. Today Monte Carlo methods are used in virtually all areas of science and engineering with problems too difficult to be addressed by other methods.
This is the complete article, containing 846 words
(approx. 3 pages at 300 words per page).
